Proper hashing for comparable object types.

Some of the existing object hash algorithms have changed, but I think
we'll live with that.

diff --git a/catacomb-python.h b/catacomb-python.h
index 2890289..9d86e57 100644 (file)
--- a/catacomb-python.h
+++ b/catacomb-python.h
@@ -44,6 +44,7 @@
 #include <mLib/dstr.h>
 #include <mLib/macros.h>
 #include <mLib/quis.h>
+#include <mLib/unihash.h>
 
 #include <catacomb/buf.h>
 

diff --git a/catacomb/__init__.py b/catacomb/__init__.py
index 6ed992e..19a973b 100644 (file)
--- a/catacomb/__init__.py
+++ b/catacomb/__init__.py
@@ -184,6 +184,7 @@ _augment(Field, _tmp)
 
 class _tmp:
   def __repr__(me): return '%s(%sL)' % (type(me).__name__, me.p)
+  def __hash__(me): return 0x114401de ^ hash(me.p)
   def ec(me, a, b): return ECPrimeProjCurve(me, a, b)
 _augment(PrimeField, _tmp)
 
@@ -193,6 +194,18 @@ class _tmp:
 _augment(BinField, _tmp)
 
 class _tmp:
+  def __hash__(me): return 0x23e4701c ^ hash(me.p)
+_augment(BinPolyField, _tmp)
+
+class _tmp:
+  def __hash__(me):
+    h = 0x9a7d6240
+    h ^=   hash(me.p)
+    h ^= 2*hash(me.beta) & 0xffffffff
+    return h
+_augment(BinNormField, _tmp)
+
+class _tmp:
   def __str__(me): return str(me.value)
   def __repr__(me): return '%s(%s)' % (repr(me.field), repr(me.value))
 _augment(FE, _tmp)
@@ -212,6 +225,24 @@ class _tmp:
 _augment(ECCurve, _tmp)
 
 class _tmp:
+  def __hash__(me):
+    h = 0x6751d341
+    h ^=   hash(me.field)
+    h ^= 2*hash(me.a) ^ 0xffffffff
+    h ^= 5*hash(me.b) ^ 0xffffffff
+    return h
+_augment(ECPrimeCurve, _tmp)
+
+class _tmp:
+  def __hash__(me):
+    h = 0x2ac203c5
+    h ^=   hash(me.field)
+    h ^= 2*hash(me.a) ^ 0xffffffff
+    h ^= 5*hash(me.b) ^ 0xffffffff
+    return h
+_augment(ECBinCurve, _tmp)
+
+class _tmp:
   def __repr__(me):
     if not me: return 'ECPt()'
     return 'ECPt(%s, %s)' % (me.ix, me.iy)
@@ -224,6 +255,11 @@ class _tmp:
   def __repr__(me):
     return 'ECInfo(curve = %r, G = %r, r = %s, h = %s)' % \
            (me.curve, me.G, me.r, me.h)
+  def __hash__(me):
+    h = 0x9bedb8de
+    h ^=   hash(me.curve)
+    h ^= 2*hash(me.G) & 0xffffffff
+    return h
   def group(me):
     return ECGroup(me)
 _augment(ECInfo, _tmp)
@@ -291,6 +327,30 @@ class _tmp:
 _augment(Group, _tmp)
 
 class _tmp:
+  def __hash__(me):
+    info = me.info
+    h = 0xbce3cfe6
+    h ^=   hash(info.p)
+    h ^= 2*hash(info.r) & 0xffffffff
+    h ^= 5*hash(info.g) & 0xffffffff
+    return h
+_augment(PrimeGroup, _tmp)
+
+class _tmp:
+  def __hash__(me):
+    info = me.info
+    h = 0x80695949
+    h ^=   hash(info.p)
+    h ^= 2*hash(info.r) & 0xffffffff
+    h ^= 5*hash(info.g) & 0xffffffff
+    return h
+_augment(BinGroup, _tmp)
+
+class _tmp:
+  def __hash__(me): return 0x0ec23dab ^ hash(me.info)
+_augment(ECGroup, _tmp)
+
+class _tmp:
   def __repr__(me):
     return '%r(%r)' % (me.group, str(me))
 _augment(GE, _tmp)

diff --git a/ec.c b/ec.c
index ef09cf8..a294f09 100644 (file)
--- a/ec.c
+++ b/ec.c
@@ -193,16 +193,20 @@ static PyObject *ecpt_pymul(PyObject *x, PyObject *y)
 
 static long ecpt_pyhash(PyObject *me)
 {
-  long i;
+  uint32 h;
+  buf b;
   ec p = EC_INIT;
+  size_t sz = 2*ECPT_C(me)->f->noctets + 1;
+  octet *q = xmalloc(sz);
 
+  h = 0xe0fdd039 + ECPT_C(me)->f->ops->ty;
+  buf_init(&b, q, sz);
   EC_OUT(ECPT_C(me), &p, ECPT_P(me));
-  i = 0xe0fdd039; /* random perturbance */
-  if (p.x) i ^= mp_tolong(p.x);
-  if (p.y) i ^= mp_tolong(p.y);
-  if (i == -1) i = -2;
+  ec_putraw(ECPT_C(me), &b, &p);
   EC_DESTROY(&p);
-  return (i);
+  xfree(q);
+  h = unihash_hash(&unihash_global, h, BBASE(&b), BLEN(&b));
+  return (h % LONG_MAX);
 }
 
 static PyObject *ecpt_pyrichcompare(PyObject *x, PyObject *y, int op)

diff --git a/field.c b/field.c
index a18a942..f17f4d9 100644 (file)
--- a/field.c
+++ b/field.c
@@ -230,11 +230,13 @@ end:
 
 static long fe_pyhash(PyObject *me)
 {
-  long i = mp_tolong(FE_X(me));
-  i ^= 0xdcf62d6c; /* random perturbance */
-  if (i == -1)
-    i = -2;
-  return (i);
+  size_t sz = FE_F(me)->noctets;
+  uint32 h = 0xe0c127ca + FE_F(me)->ops->ty;
+  octet *p = xmalloc(sz);
+  mp_storeb(FE_X(me), p, sz);
+  h = unihash_hash(&unihash_global, h, p, sz);
+  xfree(p);
+  return (h % LONG_MAX);
 }
 
 static int fe_pycoerce(PyObject **x, PyObject **y)

diff --git a/group.c b/group.c
index ac10866..13ff554 100644 (file)
--- a/group.c
+++ b/group.c
@@ -914,6 +914,20 @@ static PyObject *gget_g(PyObject *me, void *hunoz)
   G_COPY(g, x, g->g); return (ge_pywrap(me, x));
 }
 
+static long ge_pyhash(PyObject *me)
+{
+  buf b;
+  size_t sz = GE_G(me)->noctets + 4;
+  uint32 h = 0xf672c776 + GE_G(me)->ops->ty;
+  octet *p = xmalloc(sz);
+  buf_init(&b, p, sz);
+  G_TOBUF(GE_G(me), &b, GE_X(me));
+  assert(BOK(&b));
+  h = unihash_hash(&unihash_global, h, BBASE(&b), BLEN(&b));
+  xfree(p);
+  return (h % LONG_MAX);
+}
+
 static PyObject *gget_r(PyObject *me, void *hunoz)
   { return (mp_pywrap(MP_COPY(GROUP_G(me)->r))); }
 
@@ -999,7 +1013,7 @@ static PyTypeObject ge_pytype_skel = {
   &ge_pynumber,                                /* @tp_as_number@ */
   0,                                   /* @tp_as_sequence@ */
   0,                                   /* @tp_as_mapping@ */
-  0,                                   /* @tp_hash@ */
+  ge_pyhash,                           /* @tp_hash@ */
   0,                                   /* @tp_call@ */
   ge_pystr,                            /* @tp_str@ */
   0,                                   /* @tp_getattro@ */