From 6d481bc65d194c9ef8445d622b7ce85eadc46921 Mon Sep 17 00:00:00 2001 Message-Id: <6d481bc65d194c9ef8445d622b7ce85eadc46921.1715978947.git.mdw@distorted.org.uk> From: Mark Wooding Date: Fri, 10 Apr 2015 15:19:25 +0100 Subject: [PATCH] Proper hashing for comparable object types. Organization: Straylight/Edgeware From: Mark Wooding Some of the existing object hash algorithms have changed, but I think we'll live with that. --- catacomb-python.h | 1 + catacomb/__init__.py | 60 ++++++++++++++++++++++++++++++++++++++++++++ ec.c | 16 +++++++----- field.c | 12 +++++---- group.c | 16 +++++++++++- 5 files changed, 93 insertions(+), 12 deletions(-) diff --git a/catacomb-python.h b/catacomb-python.h index 2890289..9d86e57 100644 --- a/catacomb-python.h +++ b/catacomb-python.h @@ -44,6 +44,7 @@ #include #include #include +#include #include diff --git a/catacomb/__init__.py b/catacomb/__init__.py index 6ed992e..19a973b 100644 --- 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) @@ -192,6 +193,18 @@ class _tmp: def ec(me, a, b): return ECBinProjCurve(me, a, b) _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)) @@ -211,6 +224,24 @@ class _tmp: return me(*args) _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()' @@ -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) @@ -290,6 +326,30 @@ class _tmp: return '%s(%r)' % (type(me).__name__, me.info) _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)) diff --git a/ec.c b/ec.c index ef09cf8..a294f09 100644 --- 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 --- 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 --- 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@ */ -- [mdw]