From: mdw Date: Sun, 6 Oct 2002 22:52:50 +0000 (+0000) Subject: Pile of changes for supporting two's complement properly. X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/commitdiff_plain/f09e814abfcb58c0bb5423589e2940c205106e8d Pile of changes for supporting two's complement properly. --- diff --git a/mp-arith.c b/mp-arith.c index d6d892b..d31309b 100644 --- a/mp-arith.c +++ b/mp-arith.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mp-arith.c,v 1.10 2001/04/03 19:36:05 mdw Exp $ + * $Id: mp-arith.c,v 1.11 2002/10/06 22:52:50 mdw Exp $ * * Basic arithmetic on multiprecision integers * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: mp-arith.c,v $ + * Revision 1.11 2002/10/06 22:52:50 mdw + * Pile of changes for supporting two's complement properly. + * * Revision 1.10 2001/04/03 19:36:05 mdw * Add some simple bitwise operations so that Perl can use them. * @@ -76,80 +79,99 @@ /*----- Main code ---------------------------------------------------------*/ -/* --- @mp_2c@ --- * +/* --- @mp_lsl@, @mp_lsr@ --- * * - * Arguments: @mp *a@ = source + * Arguments: @mp *d@ = destination + * @mp *a@ = source + * @size_t n@ = number of bits to move * - * Returns: Result, @a@ converted to two's complement notation. + * Returns: Result, @a@ shifted left or right by @n@. */ -mp *mp_2c(mp *d, mp *a) +mp *mp_lsl(mp *d, mp *a, size_t n) { - if (!(a->f & MP_NEG)) - return (MP_COPY(a)); + MP_DEST(d, MP_LEN(a) + (n + MPW_BITS - 1) / MPW_BITS, a->f); + mpx_lsl(d->v, d->vl, a->v, a->vl, n); + d->f = a->f & (MP_NEG | MP_BURN); + MP_SHRINK(d); + return (d); +} +mp *mp_lsr(mp *d, mp *a, size_t n) +{ MP_DEST(d, MP_LEN(a), a->f); - mpx_2c(d->v, d->vl, a->v, a->vl); - d->f = a->f & MP_BURN; + mpx_lsr(d->v, d->vl, a->v, a->vl, n); + d->f = a->f & (MP_NEG | MP_BURN); MP_SHRINK(d); return (d); } -/* --- @mp_sm@ --- * +/* --- @mp_lsl2c@, @mp_lsr2c@ --- * * * Arguments: @mp *d@ = destination * @mp *a@ = source + * @size_t n@ = number of bits to move * - * Returns: Result, @a@ converted to the native signed-magnitude - * notation. + * Returns: Result, @a@ shifted left or right by @n@. Handles the + * pretence of sign-extension for negative numbers. */ -mp *mp_sm(mp *d, mp *a) +mp *mp_lsl2c(mp *d, mp *a, size_t n) { - if (!MP_LEN(a) || a->vl[-1] < MPW_MAX / 2) - return (MP_COPY(a)); + if (!(a->f & MP_NEG)) + return (mp_lsl(d, a, n)); + d = mp_not2c(d, a); + d = mp_lsl(d, d, n); + d = mp_not2c(d, d); + return (d); +} - MP_DEST(d, MP_LEN(a), a->f); - mpx_2c(d->v, d->vl, a->v, a->vl); - d->f = (a->f & (MP_BURN | MP_NEG)) ^ MP_NEG; - MP_SHRINK(d); - return (d); +mp *mp_lsr2c(mp *d, mp *a, size_t n) +{ + if (!(a->f & MP_NEG)) + return (mp_lsr(d, a, n)); + d = mp_not2c(d, a); + d = mp_lsr(d, d, n); + d = mp_not2c(d, d); + return (d); } -/* --- @mp_lsl@ --- * +/* --- @mp_testbit@ --- * * - * Arguments: @mp *d@ = destination - * @mp *a@ = source - * @size_t n@ = number of bits to move + * Arguments: @mp *x@ = a large integer + * @size_t n@ = which bit to test * - * Returns: Result, @a@ shifted left by @n@. + * Returns: Nonzero if the bit is set, zero if not. */ -mp *mp_lsl(mp *d, mp *a, size_t n) +int mp_testbit(mp *x, size_t n) { - MP_DEST(d, MP_LEN(a) + (n + MPW_BITS - 1) / MPW_BITS, a->f); - mpx_lsl(d->v, d->vl, a->v, a->vl, n); - d->f = a->f & (MP_NEG | MP_BURN); - MP_SHRINK(d); - return (d); + size_t o; + if (n > MPW_BITS * MP_LEN(x)) + return (0); + o = n / MPW_BITS; + n %= MPW_BITS; + return ((x->v[o] >> n) & 1); } -/* --- @mp_lsr@ --- * +/* --- @mp_testbit2c@ --- * * - * Arguments: @mp *d@ = destination - * @mp *a@ = source - * @size_t n@ = number of bits to move + * Arguments: @mp *x@ = a large integer + * @size_t n@ = which bit to test * - * Returns: Result, @a@ shifted left by @n@. + * Returns: Nonzero if the bit is set, zero if not. Fakes up two's + * complement representation. */ -mp *mp_lsr(mp *d, mp *a, size_t n) +int mp_testbit2c(mp *x, size_t n) { - MP_DEST(d, MP_LEN(a), a->f); - mpx_lsr(d->v, d->vl, a->v, a->vl, n); - d->f = a->f & (MP_NEG | MP_BURN); - MP_SHRINK(d); - return (d); + int r; + if (x->f & MP_NEG) + return (mp_testbit(x, n)); + x = mp_not2c(MP_NEW, x); + r = !mp_testbit(x, n); + MP_DROP(x); + return (r); } /* --- @mp_eq@ --- * @@ -179,28 +201,41 @@ int mp_cmp(const mp *a, const mp *b) return (+1); } -/* --- @mpx_and@, @mpx_or@, @mpx_xor@, @mpx_not@ --- * +/* --- @mp_bitop@ --- * * * Arguments: @mp *d@ = destination * @mp *a, *b@ = sources * - * Returns: The result of the obvious bitwise operation. + * Returns: The result of the given bitwise operation. These functions + * don't handle negative numbers at all sensibly. For that, use + * the @...2c@ variants. The functions are named after the + * truth tables they generate: + * + * a: 0011 + * b: 0101 + * @mpx_bitXXXX@ */ -#define MP_BITBINOP(name) \ +#define MP_BITBINOP(string) \ \ -mp *mp_##name(mp *d, mp *a, mp *b) \ +mp *mp_bit##string(mp *d, mp *a, mp *b) \ { \ MP_DEST(d, MAX(MP_LEN(a), MP_LEN(b)), a->f | b->f); \ - mpx_##name(d->v, d->vl, a->v, a->vl, b->v, b->vl); \ + mpx_bit##string(d->v, d->vl, a->v, a->vl, b->v, b->vl); \ d->f = (a->f | b->f) & MP_BURN; \ MP_SHRINK(d); \ return (d); \ } -MP_BITBINOP(and) -MP_BITBINOP(or) -MP_BITBINOP(xor) +MPX_DOBIN(MP_BITBINOP) + +/* --- @mp_not@ --- * + * + * Arguments: @mp *d@ = destination + * @mp *a@ = source + * + * Returns: The bitwise complement of the source. + */ mp *mp_not(mp *d, mp *a) { @@ -211,6 +246,114 @@ mp *mp_not(mp *d, mp *a) return (d); } +/* --- @mp_bitop2c@ --- * + * + * Arguments: @mp *d@ = destination + * @mp *a, *b@ = sources + * + * Returns: The result of the given bitwise operation. Negative numbers + * are treated as two's complement, sign-extended infinitely to + * the left. The functions are named after the truth tables + * they generate: + * + * a: 0011 + * b: 0101 + * @mpx_bitXXXX@ + */ + +/* --- How this actually works --- * + * + * The two arguments are inverted (with a sign-swap) if they're currently + * negative. This means that we end up using a different function (one which + * reinverts as we go) for the main operation. Also, if the sign would be + * negative at the end, we preinvert the output and then invert again with a + * sign-swap. + * + * Start with: wxyz WXYZ + * If @a@ negative: yzwx or YZWX + * If @b@ negative: xwzy XWZY + * If both negative: zyxw ZYXW + */ + +#define MP_BIT2CBINOP(n, base, an, bn, abn, p_base, p_an, p_bn, p_abn) \ + \ +mp *mp_bit##n##2c(mp *d, mp *a, mp *b) \ +{ \ + if (!((a->f | b->f) & MP_NEG)) { /* Both positive */ \ + d = mp_bit##base(d, a, b); \ + p_base \ + } else if (!(b->f & MP_NEG)) { /* Only @b@ positive */ \ + MP_COPY(b); \ + d = mp_not2c(d, a); \ + d = mp_bit##an(d, d, b); \ + MP_DROP(b); \ + p_an \ + } else if (!(a->f & MP_NEG)) { /* Only @a@ positive */ \ + MP_COPY(a); \ + d = mp_not2c(d, b); \ + d = mp_bit##bn(d, a, d); \ + MP_DROP(a); \ + p_bn \ + } else { /* Both negative */ \ + mp *t = mp_not2c(MP_NEW, a); \ + mp *d = mp_not2c(d, b); \ + d = mp_bit##abn(d, t, d); \ + MP_DROP(t); \ + p_abn \ + } \ + return (d); \ +} \ + +#define NEG d = mp_not2c(d, d); +#define POS +MP_BIT2CBINOP(0000, 0000, 0000, 0000, 0000, POS, POS, POS, POS) +MP_BIT2CBINOP(0001, 0001, 0100, 0010, 0111, POS, POS, POS, NEG) +MP_BIT2CBINOP(0010, 0010, 0111, 0001, 0100, POS, NEG, POS, POS) +MP_BIT2CBINOP(0011, 0011, 0011, 0011, 0011, POS, NEG, POS, NEG) +MP_BIT2CBINOP(0100, 0100, 0001, 0111, 0010, POS, POS, NEG, POS) +MP_BIT2CBINOP(0101, 0101, 0101, 0101, 0101, POS, POS, NEG, NEG) +MP_BIT2CBINOP(0110, 0110, 0110, 0110, 0110, POS, NEG, NEG, POS) +MP_BIT2CBINOP(0111, 0111, 0010, 0100, 0001, POS, NEG, NEG, NEG) +MP_BIT2CBINOP(1000, 0111, 0010, 0100, 0001, NEG, POS, POS, POS) +MP_BIT2CBINOP(1001, 0110, 0110, 0110, 0110, NEG, POS, POS, NEG) +MP_BIT2CBINOP(1010, 0101, 0101, 0101, 0101, NEG, NEG, POS, POS) +MP_BIT2CBINOP(1011, 0100, 0001, 0111, 0010, NEG, NEG, POS, NEG) +MP_BIT2CBINOP(1100, 0011, 0011, 0011, 0011, NEG, POS, NEG, POS) +MP_BIT2CBINOP(1101, 0010, 0111, 0001, 0100, NEG, POS, NEG, NEG) +MP_BIT2CBINOP(1110, 0001, 0100, 0010, 0111, NEG, NEG, NEG, POS) +MP_BIT2CBINOP(1111, 0000, 0000, 0000, 0000, NEG, NEG, NEG, NEG) +#undef NEG +#undef POS + +/* --- @mp_not2c@ --- * + * + * Arguments: @mp *d@ = destination + * @mp *a@ = source + * + * Returns: The sign-extended complement of the argument. + */ + +mp *mp_not2c(mp *d, mp *a) +{ + mpw one = 1; + + MP_DEST(d, MP_LEN(a) + 1, a->f); + if (d == a) { + if (a->f & MP_NEG) + MPX_USUBN(d->v, d->vl, 1); + else + MPX_UADDN(d->v, d->vl, 1); + } else { + if (a->f & MP_NEG) + mpx_usub(d->v, d->vl, a->v, a->vl, &one, &one + 1); + else + mpx_uadd(d->v, d->vl, a->v, a->vl, &one, &one + 1); + } + d->f = (a->f & (MP_NEG | MP_BURN)) ^ MP_NEG; + MP_SHRINK(d); + return (d); +} + /* --- @mp_add@ --- * * * Arguments: @mp *d@ = destination @@ -498,6 +641,8 @@ static int verify(const char *op, mp *expect, mp *result, mp *a, mp *b) RIG(lsl, mp_lsl) RIG(lsr, mp_lsr) +RIG(lsl2c, mp_lsl2c) +RIG(lsr2c, mp_lsr2c) #undef RIG @@ -536,6 +681,41 @@ static int tdiv(dstr *v) return (ok); } +static int tbin(dstr *v) +{ + static mp *(*fn[])(mp *, mp *, mp *) = { +#define DO(string) mp_bit##string##2c, +MPX_DOBIN(DO) +#undef DO + }; + int ok = 1; + unsigned op = 0; + mp *a = *(mp **)v[1].buf; + mp *b = *(mp **)v[2].buf; + mp *r = *(mp **)v[3].buf; + mp *c; + + if (strcmp(v[0].buf, "and") == 0) op = 1; + else if (strcmp(v[0].buf, "or") == 0) op = 7; + else if (strcmp(v[0].buf, "nand") == 0) op = 14; + else if (strcmp(v[0].buf, "nor") == 0) op = 8; + else if (strcmp(v[0].buf, "xor") == 0) op = 6; + else { + char *p = v[0].buf; + while (*p) { + op <<= 1; + if (*p++ == '1') + op |= 1; + } + } + + c = fn[op](MP_NEW, a, b); + ok = verify(v[0].buf, r, c, a, b); + mp_drop(a); mp_drop(b); mp_drop(r); mp_drop(c); + assert(mparena_count(MPARENA_GLOBAL) == 0); + return (ok); +} + static int todd(dstr *v) { mp *a = *(mp **)v[0].buf; @@ -562,12 +742,15 @@ static int todd(dstr *v) } static test_chunk tests[] = { - { "lsl", tlsl, { &type_mp, &type_mp, &type_mp, 0 } }, - { "lsr", tlsr, { &type_mp, &type_mp, &type_mp, 0 } }, + { "lsl", tlsl, { &type_mp, &type_int, &type_mp, 0 } }, + { "lsr", tlsr, { &type_mp, &type_int, &type_mp, 0 } }, + { "lsl2c", tlsl2c, { &type_mp, &type_int, &type_mp, 0 } }, + { "lsr2c", tlsr2c, { &type_mp, &type_int, &type_mp, 0 } }, { "add", tadd, { &type_mp, &type_mp, &type_mp, 0 } }, { "sub", tsub, { &type_mp, &type_mp, &type_mp, 0 } }, { "mul", tmul, { &type_mp, &type_mp, &type_mp, 0 } }, { "div", tdiv, { &type_mp, &type_mp, &type_mp, &type_mp, 0 } }, + { "bin2c", tbin, { &type_string, &type_mp, &type_mp, &type_mp, 0 } }, { "odd", todd, { &type_mp, &type_uint32, &type_mp, 0 } }, { 0, 0, { 0 } }, }; diff --git a/mp-io.c b/mp-io.c index c510649..2f87892 100644 --- a/mp-io.c +++ b/mp-io.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mp-io.c,v 1.4 2000/06/17 11:45:09 mdw Exp $ + * $Id: mp-io.c,v 1.5 2002/10/06 22:52:50 mdw Exp $ * * Loading and storing of multiprecision integers * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: mp-io.c,v $ + * Revision 1.5 2002/10/06 22:52:50 mdw + * Pile of changes for supporting two's complement properly. + * * Revision 1.4 2000/06/17 11:45:09 mdw * Major memory management overhaul. Added arena support. Use the secure * arena for secret integers. Replace and improve the MP management macros @@ -69,6 +72,23 @@ size_t mp_octets(const mp *m) return (sz); } +/* --- @mp_octets2c@ --- * + * + * Arguments: @const mp *m@ = a multiprecision integer + * + * Returns: The number of octets required to represent @m@. + * + * Use: Calculates the external storage required for a multiprecision + * integer represented as two's complement. + */ + +size_t mp_octets2c(const mp *m) +{ + size_t sz; + MPX_OCTETS2C(sz, m->v, m->vl); + return (sz); +} + /* --- @mp_bits@ --- * * * Arguments: @const mp *m@ = a multiprecision integer @@ -176,4 +196,108 @@ void mp_storeb(const mp *m, void *pv, size_t sz) mpx_storeb(m->v, m->vl, pv, sz); } +/* --- @mp_loadl2c@ --- * + * + * Arguments: @mp *d@ = destination + * @const void *pv@ = pointer to source data + * @size_t sz@ = size of the source data + * + * Returns: Resulting multiprecision number. + * + * Use: Loads a multiprecision number from an array of octets as + * two's complement. The first byte in the array is the least + * significant. + */ + +mp *mp_loadl2c(mp *d, const void *pv, size_t sz) +{ + const octet *ov = pv; + MP_DEST(d, MPW_RQ(sz), MP_UNDEF); + if (!sz || !(ov[sz - 1] & 0x80)) { + mpx_loadl(d->v, d->vl, pv, sz); + d->f &= ~MP_NEG; + } else { + mpx_loadl2cn(d->v, d->vl, pv, sz); + d->f |= MP_NEG; + } + d->f &= ~MP_UNDEF; + mp_shrink(d); + return (d); +} + +/* --- @mp_storel2c@ --- * + * + * Arguments: @const mp *m@ = source + * @void *pv@ = pointer to output array + * @size_t sz@ = size of the output array + * + * Returns: --- + * + * Use: Stores a multiprecision number in an array of octets as two's + * complement. The first byte in the array is the least + * significant. If the array is too small to represent the + * number, high-order bits are truncated; if the array is too + * large, high order bytes are sign-extended. + */ + +void mp_storel2c(const mp *m, void *pv, size_t sz) +{ + if (m->f & MP_NEG) + mpx_storel2cn(m->v, m->vl, pv, sz); + else + mpx_storel(m->v, m->vl, pv, sz); +} + +/* --- @mp_loadb2c@ --- * + * + * Arguments: @mp *d@ = destination + * @const void *pv@ = pointer to source data + * @size_t sz@ = size of the source data + * + * Returns: Resulting multiprecision number. + * + * Use: Loads a multiprecision number from an array of octets as + * two's complement. The last byte in the array is the least + * significant. + */ + +mp *mp_loadb2c(mp *d, const void *pv, size_t sz) +{ + const octet *ov = pv; + MP_DEST(d, MPW_RQ(sz), MP_UNDEF); + if (!sz || !(ov[0] & 0x80)) { + mpx_loadl(d->v, d->vl, pv, sz); + d->f &= ~MP_NEG; + } else { + mpx_loadl2cn(d->v, d->vl, pv, sz); + d->f |= MP_NEG; + } + d->f &= ~MP_UNDEF; + mp_shrink(d); + return (d); +} + +/* --- @mp_storeb2c@ --- * + * + * Arguments: @const mp *m@ = source + * @void *pv@ = pointer to output array + * @size_t sz@ = size of the output array + * + * Returns: --- + * + * Use: Stores a multiprecision number in an array of octets, as + * two's complement. The last byte in the array is the least + * significant. If the array is too small to represent the + * number, high-order bits are truncated; if the array is too + * large, high order bytes are sign-extended. + */ + +void mp_storeb2c(const mp *m, void *pv, size_t sz) +{ + if (m->f & MP_NEG) + mpx_storeb2cn(m->v, m->vl, pv, sz); + else + mpx_storeb(m->v, m->vl, pv, sz); +} + /*----- That's all, folks -------------------------------------------------*/ diff --git a/mp.h b/mp.h index 71092fd..c405bca 100644 --- a/mp.h +++ b/mp.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mp.h,v 1.12 2001/06/16 12:57:43 mdw Exp $ + * $Id: mp.h,v 1.13 2002/10/06 22:52:50 mdw Exp $ * * Simple multiprecision arithmetic * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: mp.h,v $ + * Revision 1.13 2002/10/06 22:52:50 mdw + * Pile of changes for supporting two's complement properly. + * * Revision 1.12 2001/06/16 12:57:43 mdw * Move the @mpmont_factor@ structure and rename it now that it's used for * Barrett simultaneous exponentiation too. @@ -492,6 +495,18 @@ extern void mp_rscan(mpscan */*sc*/, const mp */*m*/); extern size_t mp_octets(const mp */*m*/); +/* --- @mp_octets2c@ --- * + * + * Arguments: @const mp *m@ = a multiprecision integer + * + * Returns: The number of octets required to represent @m@. + * + * Use: Calculates the external storage required for a multiprecision + * integer represented as two's complement. + */ + +extern size_t mp_octets2c(const mp */*m*/); + /* --- @mp_bits@ --- * * * Arguments: @const mp *m@ = a multiprecision integer @@ -574,50 +589,117 @@ extern mp *mp_loadb(mp */*d*/, const void */*pv*/, size_t /*sz*/); extern void mp_storeb(const mp */*m*/, void */*pv*/, size_t /*sz*/); -/*----- Simple arithmetic -------------------------------------------------*/ - -/* --- @mp_2c@ --- * +/* --- @mp_loadl2c@ --- * * * Arguments: @mp *d@ = destination - * @mp *a@ = source + * @const void *pv@ = pointer to source data + * @size_t sz@ = size of the source data + * + * Returns: Resulting multiprecision number. * - * Returns: Result, @a@ converted to two's complement notation. + * Use: Loads a multiprecision number from an array of octets as + * two's complement. The first byte in the array is the least + * significant. */ -extern mp *mp_2c(mp */*d*/, mp */*a*/); +extern mp *mp_loadl2c(mp */*d*/, const void */*pv*/, size_t /*sz*/); -/* --- @mp_sm@ --- * +/* --- @mp_storel2c@ --- * + * + * Arguments: @const mp *m@ = source + * @void *pv@ = pointer to output array + * @size_t sz@ = size of the output array + * + * Returns: --- + * + * Use: Stores a multiprecision number in an array of octets as two's + * complement. The first byte in the array is the least + * significant. If the array is too small to represent the + * number, high-order bits are truncated; if the array is too + * large, high order bytes are sign-extended. + */ + +extern void mp_storel2c(const mp */*m*/, void */*pv*/, size_t /*sz*/); + +/* --- @mp_loadb2c@ --- * * * Arguments: @mp *d@ = destination - * @mp *a@ = source + * @const void *pv@ = pointer to source data + * @size_t sz@ = size of the source data * - * Returns: Result, @a@ converted to the native signed-magnitude - * notation. + * Returns: Resulting multiprecision number. + * + * Use: Loads a multiprecision number from an array of octets as + * two's complement. The last byte in the array is the least + * significant. */ -extern mp *mp_sm(mp */*d*/, mp */*a*/); +extern mp *mp_loadb2c(mp */*d*/, const void */*pv*/, size_t /*sz*/); + +/* --- @mp_storeb2c@ --- * + * + * Arguments: @const mp *m@ = source + * @void *pv@ = pointer to output array + * @size_t sz@ = size of the output array + * + * Returns: --- + * + * Use: Stores a multiprecision number in an array of octets, as + * two's complement. The last byte in the array is the least + * significant. If the array is too small to represent the + * number, high-order bits are truncated; if the array is too + * large, high order bytes are sign-extended. + */ + +extern void mp_storeb2c(const mp */*m*/, void */*pv*/, size_t /*sz*/); + +/*----- Simple arithmetic -------------------------------------------------*/ -/* --- @mp_lsl@ --- * +/* --- @mp_lsl@, @mp_lsr@ --- * * * Arguments: @mp *d@ = destination * @mp *a@ = source * @size_t n@ = number of bits to move * - * Returns: Result, @a@ shifted left by @n@. + * Returns: Result, @a@ shifted left or right by @n@. */ extern mp *mp_lsl(mp */*d*/, mp */*a*/, size_t /*n*/); +extern mp *mp_lsr(mp */*d*/, mp */*a*/, size_t /*n*/); -/* --- @mp_lsr@ --- * +/* --- @mp_lsl2c@, @mp_lsr2c@ --- * * * Arguments: @mp *d@ = destination * @mp *a@ = source * @size_t n@ = number of bits to move * - * Returns: Result, @a@ shifted left by @n@. + * Returns: Result, @a@ shifted left or right by @n@. Handles the + * pretence of sign-extension for negative numbers. */ -extern mp *mp_lsr(mp */*d*/, mp */*a*/, size_t /*n*/); +extern mp *mp_lsl2c(mp */*d*/, mp */*a*/, size_t /*n*/); +extern mp *mp_lsr2c(mp */*d*/, mp */*a*/, size_t /*n*/); + +/* --- @mp_testbit@ --- * + * + * Arguments: @mp *x@ = a large integer + * @size_t n@ = which bit to test + * + * Returns: Nonzero if the bit is set, zero if not. + */ + +extern int mp_testbit(mp */*x*/, size_t /*n*/); + +/* --- @mp_testbit2c@ --- * + * + * Arguments: @mp *x@ = a large integer + * @size_t n@ = which bit to test + * + * Returns: Nonzero if the bit is set, zero if not. Fakes up two's + * complement representation. + */ + +extern int mp_testbit2c(mp */*x*/, size_t /*n*/); /* --- @mp_eq@ --- * * @@ -644,19 +726,86 @@ extern int mp_cmp(const mp */*a*/, const mp */*b*/); #define MP_CMP(a, op, b) (mp_cmp((a), (b)) op 0) -/* --- @mpx_and@, @mpx_or@, @mpx_xor@, @mpx_not@ --- * +/* --- @mp_bitop@ --- * * * Arguments: @mp *d@ = destination * @mp *a, *b@ = sources * - * Returns: The result of the obvious bitwise operation. + * Returns: The result of the given bitwise operation. These functions + * don't handle negative numbers at all sensibly. For that, use + * the @...2c@ variants. The functions are named after the + * truth tables they generate: + * + * a: 0011 + * b: 0101 + * @mpx_bitXXXX@ */ -extern mp *mp_and(mp */*d*/, mp */*a*/, mp */*b*/); -extern mp *mp_or(mp */*d*/, mp */*a*/, mp */*b*/); -extern mp *mp_xor(mp */*d*/, mp */*a*/, mp */*b*/); +#define MP_BITDECL(string) \ + extern mp *mp_bit##string(mp */*d*/, mp */*a*/, mp */*b*/); +MPX_DOBIN(MP_BITDECL) + +/* --- @mp_[n]and@, @mp_[n]or@, @mp_[n]xor@, @mp_not@ --- * + * + * Synonyms for the commonly-used functions. + */ + +#define mp_and mp_bit0001 +#define mp_or mp_bit0111 +#define mp_nand mp_bit1110 +#define mp_nor mp_bit1000 +#define mp_xor mp_bit0110 + +/* --- @mp_not@ --- * + * + * Arguments: @mp *d@ = destination + * @mp *a@ = source + * + * Returns: The bitwise complement of the source. + */ + extern mp *mp_not(mp */*d*/, mp */*a*/); +/* --- @mp_bitop2c@ --- * + * + * Arguments: @mp *d@ = destination + * @mp *a, *b@ = sources + * + * Returns: The result of the given bitwise operation. Negative numbers + * are treated as two's complement, sign-extended infinitely to + * the left. The functions are named after the truth tables + * they generate: + * + * a: 0011 + * b: 0101 + * @mpx_bitXXXX@ + */ + +#define MP_BIT2CDECL(string) \ + extern mp *mp_bit##string##2c(mp */*d*/, mp */*a*/, mp */*b*/); +MPX_DOBIN(MP_BIT2CDECL) + +/* --- @mp_[n]and@, @mp_[n]or@, @mp_[n]xor@, @mp_not@ --- * + * + * Synonyms for the commonly-used functions. + */ + +#define mp_and2c mp_bit00012c +#define mp_or2c mp_bit01112c +#define mp_nand2c mp_bit11102c +#define mp_nor2c mp_bit10002c +#define mp_xor2c mp_bit01102c + +/* --- @mp_not2c@ --- * + * + * Arguments: @mp *d@ = destination + * @mp *a@ = source + * + * Returns: The sign-extended complement of the argument. + */ + +extern mp *mp_not2c(mp */*d*/, mp */*a*/); + /* --- @mp_add@ --- * * * Arguments: @mp *d@ = destination diff --git a/mpx.c b/mpx.c index f89a89b..4097b3e 100644 --- a/mpx.c +++ b/mpx.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mpx.c,v 1.11 2001/04/03 19:36:05 mdw Exp $ + * $Id: mpx.c,v 1.12 2002/10/06 22:52:50 mdw Exp $ * * Low-level multiprecision arithmetic * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: mpx.c,v $ + * Revision 1.12 2002/10/06 22:52:50 mdw + * Pile of changes for supporting two's complement properly. + * * Revision 1.11 2001/04/03 19:36:05 mdw * Add some simple bitwise operations so that Perl can use them. * @@ -233,6 +236,186 @@ void mpx_loadb(mpw *v, mpw *vl, const void *pp, size_t sz) MPX_ZERO(v, vl); } +/* --- @mpx_storel2cn@ --- * + * + * Arguments: @const mpw *v, *vl@ = base and limit of source vector + * @void *pp@ = pointer to octet array + * @size_t sz@ = size of octet array + * + * Returns: --- + * + * Use: Stores a negative MP in an octet array, least significant + * octet first, as two's complement. High-end octets are + * silently discarded if there isn't enough space for them. + * This obviously makes the output bad. + */ + +void mpx_storel2cn(const mpw *v, const mpw *vl, void *pp, size_t sz) +{ + unsigned c = 1; + unsigned b = 0; + mpw n, w = 0; + octet *p = pp, *q = p + sz; + unsigned bits = 0; + + while (p < q) { + if (bits < 8) { + if (v >= vl) { + b = w; + break; + } + n = *v++; + b = w | n << bits; + w = n >> (8 - bits); + bits += MPW_BITS - 8; + } else { + b = w; + w >>= 8; + bits -= 8; + } + b = U8(~b + c); + c = !b; + *p++ = b; + } + while (p < q) { + b = U8(~b + c); + c = !b; + *p++ = b; + b = 0; + } +} + +/* --- @mpx_loadl2cn@ --- * + * + * Arguments: @mpw *v, *vl@ = base and limit of destination vector + * @const void *pp@ = pointer to octet array + * @size_t sz@ = size of octet array + * + * Returns: --- + * + * Use: Loads a negative MP in an octet array, least significant + * octet first, as two's complement. High-end octets are + * ignored if there isn't enough space for them. This probably + * means you made the wrong choice coming here. + */ + +void mpx_loadl2cn(mpw *v, mpw *vl, const void *pp, size_t sz) +{ + unsigned n; + unsigned c = 1; + mpw w = 0; + const octet *p = pp, *q = p + sz; + unsigned bits = 0; + + if (v >= vl) + return; + while (p < q) { + n = U8(~(*p++) + c); + c = !n; + w |= n << bits; + bits += 8; + if (bits >= MPW_BITS) { + *v++ = MPW(w); + w = n >> (MPW_BITS - bits + 8); + bits -= MPW_BITS; + if (v >= vl) + return; + } + } + *v++ = w; + MPX_ZERO(v, vl); +} + +/* --- @mpx_storeb2cn@ --- * + * + * Arguments: @const mpw *v, *vl@ = base and limit of source vector + * @void *pp@ = pointer to octet array + * @size_t sz@ = size of octet array + * + * Returns: --- + * + * Use: Stores a negative MP in an octet array, most significant + * octet first, as two's complement. High-end octets are + * silently discarded if there isn't enough space for them, + * which probably isn't what you meant. + */ + +void mpx_storeb2cn(const mpw *v, const mpw *vl, void *pp, size_t sz) +{ + mpw n, w = 0; + unsigned b = 0; + unsigned c = 1; + octet *p = pp, *q = p + sz; + unsigned bits = 0; + + while (q > p) { + if (bits < 8) { + if (v >= vl) { + b = w; + break; + } + n = *v++; + b = w | n << bits; + w = n >> (8 - bits); + bits += MPW_BITS - 8; + } else { + b = w; + w >>= 8; + bits -= 8; + } + b = U8(~b + c); + c = !b; + *--q = b; + } + while (q > p) { + b = ~b + c; + c = !(b & 0xff); + *--q = b; + b = 0; + } +} + +/* --- @mpx_loadb2cn@ --- * + * + * Arguments: @mpw *v, *vl@ = base and limit of destination vector + * @const void *pp@ = pointer to octet array + * @size_t sz@ = size of octet array + * + * Returns: --- + * + * Use: Loads a negative MP in an octet array, most significant octet + * first as two's complement. High-end octets are ignored if + * there isn't enough space for them. This probably means you + * chose this function wrongly. + */ + +void mpx_loadb2cn(mpw *v, mpw *vl, const void *pp, size_t sz) +{ + unsigned n; + unsigned c = 1; + mpw w = 0; + const octet *p = pp, *q = p + sz; + unsigned bits = 0; + + if (v >= vl) + return; + while (q > p) { + n = U8(~(*--q) + c); + c = !n; + w |= n << bits; + bits += 8; + if (bits >= MPW_BITS) { + *v++ = MPW(w); + w = n >> (MPW_BITS - bits + 8); + bits -= MPW_BITS; + if (v >= vl) + return; + } + } + *v++ = w; + MPX_ZERO(v, vl); +} + /*----- Logical shifting --------------------------------------------------*/ /* --- @mpx_lsl@ --- * @@ -405,7 +588,7 @@ done:; /*----- Bitwise operations ------------------------------------------------*/ -/* --- @mpx_and@, @mpx_or@, @mpx_xor@, @mpx_not@ --- * +/* --- @mpx_bitop@ --- * * * Arguments: @mpw *dv, *dvl@ = destination vector * @const mpw *av, *avl@ = first source vector @@ -413,13 +596,13 @@ done:; * * Returns: --- * - * Use; Does the obvious bitwise operations. + * Use; Provides the dyadic boolean functions. */ -#define MPX_BITBINOP(name, op) \ +#define MPX_BITBINOP(string) \ \ -void mpx_##name(mpw *dv, mpw *dvl, const mpw *av, const mpw *avl, \ - const mpw *bv, const mpw *bvl) \ +void mpx_bit##string(mpw *dv, mpw *dvl, const mpw *av, const mpw *avl, \ + const mpw *bv, const mpw *bvl) \ { \ MPX_SHRINK(av, avl); \ MPX_SHRINK(bv, bvl); \ @@ -428,13 +611,11 @@ void mpx_##name(mpw *dv, mpw *dvl, const mpw *av, const mpw *avl, \ mpw a, b; \ a = (av < avl) ? *av++ : 0; \ b = (bv < bvl) ? *bv++ : 0; \ - *dv++ = a op b; \ + *dv++ = MPX_B##string(a, b); \ } \ } -MPX_BITBINOP(and, &) -MPX_BITBINOP(or, |) -MPX_BITBINOP(xor, ^) +MPX_DOBIN(MPX_BITBINOP) void mpx_not(mpw *dv, mpw *dvl, const mpw *av, const mpw *avl) { @@ -1130,6 +1311,84 @@ static int loadstore(dstr *v) return (ok); } +static int twocl(dstr *v) +{ + dstr d = DSTR_INIT; + mpw *m, *ml; + size_t sz; + int ok = 1; + + sz = v[0].len; if (v[1].len > sz) sz = v[1].len; + dstr_ensure(&d, sz); + + sz = MPW_RQ(sz); + m = xmalloc(MPWS(sz)); + ml = m + sz; + + mpx_loadl(m, ml, v[0].buf, v[0].len); + mpx_storel2cn(m, ml, d.buf, v[1].len); + if (memcmp(d.buf, v[1].buf, v[1].len)) { + dumpbits("\n*** storel2cn failed", d.buf, v[1].len); + ok = 0; + } + + mpx_loadl2cn(m, ml, v[1].buf, v[1].len); + mpx_storel(m, ml, d.buf, v[0].len); + if (memcmp(d.buf, v[0].buf, v[0].len)) { + dumpbits("\n*** loadl2cn failed", d.buf, v[0].len); + ok = 0; + } + + if (!ok) { + dumpbits("pos", v[0].buf, v[0].len); + dumpbits("neg", v[1].buf, v[1].len); + } + + free(m); + dstr_destroy(&d); + + return (ok); +} + +static int twocb(dstr *v) +{ + dstr d = DSTR_INIT; + mpw *m, *ml; + size_t sz; + int ok = 1; + + sz = v[0].len; if (v[1].len > sz) sz = v[1].len; + dstr_ensure(&d, sz); + + sz = MPW_RQ(sz); + m = xmalloc(MPWS(sz)); + ml = m + sz; + + mpx_loadb(m, ml, v[0].buf, v[0].len); + mpx_storeb2cn(m, ml, d.buf, v[1].len); + if (memcmp(d.buf, v[1].buf, v[1].len)) { + dumpbits("\n*** storeb2cn failed", d.buf, v[1].len); + ok = 0; + } + + mpx_loadb2cn(m, ml, v[1].buf, v[1].len); + mpx_storeb(m, ml, d.buf, v[0].len); + if (memcmp(d.buf, v[0].buf, v[0].len)) { + dumpbits("\n*** loadb2cn failed", d.buf, v[0].len); + ok = 0; + } + + if (!ok) { + dumpbits("pos", v[0].buf, v[0].len); + dumpbits("neg", v[1].buf, v[1].len); + } + + free(m); + dstr_destroy(&d); + + return (ok); +} + static int lsl(dstr *v) { mpw *a, *al; @@ -1320,6 +1579,8 @@ static int udiv(dstr *v) static test_chunk defs[] = { { "load-store", loadstore, { &type_hex, 0 } }, + { "2cl", twocl, { &type_hex, &type_hex, } }, + { "2cb", twocb, { &type_hex, &type_hex, } }, { "lsl", lsl, { &type_hex, &type_int, &type_hex, 0 } }, { "lsr", lsr, { &type_hex, &type_int, &type_hex, 0 } }, { "uadd", uadd, { &type_hex, &type_hex, &type_hex, 0 } }, diff --git a/mpx.h b/mpx.h index b633e43..948e7dd 100644 --- a/mpx.h +++ b/mpx.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mpx.h,v 1.12 2001/04/03 19:36:05 mdw Exp $ + * $Id: mpx.h,v 1.13 2002/10/06 22:52:50 mdw Exp $ * * Low level multiprecision arithmetic * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: mpx.h,v $ + * Revision 1.13 2002/10/06 22:52:50 mdw + * Pile of changes for supporting two's complement properly. + * * Revision 1.12 2001/04/03 19:36:05 mdw * Add some simple bitwise operations so that Perl can use them. * @@ -151,25 +154,24 @@ */ #define MPX_OCTETS(o, v, vl) do { \ - const mpw *_v = (v), *_vl = (vl); \ - MPX_SHRINK(_v, _vl); \ - if (_v == _vl) \ - (o) = 0; \ - else { \ - size_t _o = (MPW_BITS / 8) * (_vl - _v - 1); \ - mpw _w = _vl[-1]; \ - unsigned _k = MPW_BITS / 2; \ - while (_k >= 8) { \ - if (_w >> _k) { \ - _w >>= _k; \ - _o += _k >> 3; \ - } \ - _k >>= 1; \ - } \ - if (_w) \ - _o++; \ - (o) = _o; \ - } \ + unsigned long _bb; \ + MPX_BITS(_bb, (v), (vl)); \ + (o) = (_bb + 7) >> 3; \ +} while (0) + +/* --- @MPX_OCTETS2C@ --- * + * + * Arguments: @size_t o@ = result variable + * @const mpw *v, *vl@ = pointer to array of words + * + * Use: Calculates the number of octets in a multiprecision value, if + * you represent it as two's complement. + */ + +#define MPX_OCTETS2C(o, v, vl) do { \ + unsigned long _bb; \ + MPX_BITS(_bb, (v), (vl)); \ + (o) = (_bb >> 3) + 1; \ } while (0) /* --- @MPX_COPY@ --- * @@ -275,6 +277,75 @@ extern void mpx_storeb(const mpw */*v*/, const mpw */*vl*/, extern void mpx_loadb(mpw */*v*/, mpw */*vl*/, const void */*p*/, size_t /*sz*/); +/* --- @mpx_storel2cn@ --- * + * + * Arguments: @const mpw *v, *vl@ = base and limit of source vector + * @void *pp@ = pointer to octet array + * @size_t sz@ = size of octet array + * + * Returns: --- + * + * Use: Stores a negative MP in an octet array, least significant + * octet first, as two's complement. High-end octets are + * silently discarded if there isn't enough space for them. + * This obviously makes the output bad. + */ + +extern void mpx_storel2cn(const mpw */*v*/, const mpw */*vl*/, + void */*p*/, size_t /*sz*/); + +/* --- @mpx_loadl2cn@ --- * + * + * Arguments: @mpw *v, *vl@ = base and limit of destination vector + * @const void *pp@ = pointer to octet array + * @size_t sz@ = size of octet array + * + * Returns: --- + * + * Use: Loads a negative MP in an octet array, least significant + * octet first, as two's complement. High-end octets are + * ignored if there isn't enough space for them. This probably + * means you made the wrong choice coming here. + */ + +extern void mpx_loadl2cn(mpw */*v*/, mpw */*vl*/, + const void */*p*/, size_t /*sz*/); + +/* --- @mpx_storeb2cn@ --- * + * + * Arguments: @const mpw *v, *vl@ = base and limit of source vector + * @void *pp@ = pointer to octet array + * @size_t sz@ = size of octet array + * + * Returns: --- + * + * Use: Stores a negative MP in an octet array, most significant + * octet first, as two's complement. High-end octets are + * silently discarded if there isn't enough space for them, + * which probably isn't what you meant. + */ + +extern void mpx_storeb2cn(const mpw */*v*/, const mpw */*vl*/, + void */*p*/, size_t /*sz*/); + +/* --- @mpx_loadb2cn@ --- * + * + * Arguments: @mpw *v, *vl@ = base and limit of destination vector + * @const void *pp@ = pointer to octet array + * @size_t sz@ = size of octet array + * + * Returns: --- + * + * Use: Loads a negative MP in an octet array, most significant octet + * first as two's complement. High-end octets are ignored if + * there isn't enough space for them. This probably means you + * chose this function wrongly. + */ + +extern void mpx_loadb2cn(mpw */*v*/, mpw */*vl*/, + const void */*p*/, size_t /*sz*/); + + /*----- Logical shifting --------------------------------------------------*/ /* --- @mpx_lsl@ --- * @@ -309,7 +380,30 @@ extern void mpx_lsr(mpw */*dv*/, mpw */*dvl*/, /*----- Bitwise operations ------------------------------------------------*/ -/* --- @mpx_and@, @mpx_or@, @mpx_xor@, @mpx_not@ --- * +/* --- How to implement them --- * + * + * x: 0011 + * y: 0101 + */ + +#define MPX_B0000(x, y) (0u) +#define MPX_B0001(x, y) ((x) & (y)) +#define MPX_B0010(x, y) ((x) & ~(y)) +#define MPX_B0011(x, y) (x) +#define MPX_B0100(x, y) (~(x) & ~(y)) +#define MPX_B0101(x, y) (y) +#define MPX_B0110(x, y) ((x) ^ (y)) +#define MPX_B0111(x, y) ((x) | (y)) +#define MPX_B1000(x, y) (~((x) | (y))) +#define MPX_B1001(x, y) (~((x) ^ (y))) +#define MPX_B1010(x, y) (~(y)) +#define MPX_B1011(x, y) ((x) | ~(y)) +#define MPX_B1100(x, y) (~(x)) +#define MPX_B1101(x, y) (~(x) | (y)) +#define MPX_B1110(x, y) (~((x) & (y))) +#define MPX_B1111(x, y) (~0u) + +/* --- @mpx_bitop@ --- * * * Arguments: @mpw *dv, *dvl@ = destination vector * @const mpw *av, *avl@ = first source vector @@ -317,20 +411,46 @@ extern void mpx_lsr(mpw */*dv*/, mpw */*dvl*/, * * Returns: --- * - * Use; Does the obvious bitwise operations. + * Use: Provide the dyadic boolean functions. The functions are + * named after the truth table they generate: + * + * a: 0011 + * b: 0101 + * @mpx_bitXXXX@ */ -extern void mpx_and(mpw */*dv*/, mpw */*dvl*/, - const mpw */*av*/, const mpw */*avl*/, - const mpw */*bv*/, const mpw */*bvl*/); +#define MPX_DOBIN(what) \ + what(0000) what(0001) what(0010) what(0011) \ + what(0100) what(0101) what(0110) what(0111) \ + what(1000) what(1001) what(1010) what(1011) \ + what(1100) what(1101) what(1110) what(1111) -extern void mpx_or(mpw */*dv*/, mpw */*dvl*/, - const mpw */*av*/, const mpw */*avl*/, - const mpw */*bv*/, const mpw */*bvl*/); +#define MPX_BITDECL(string) \ + extern void mpx_bit##string(mpw */*dv*/, mpw */*dvl*/, \ + const mpw */*av*/, const mpw */*avl*/, \ + const mpw */*bv*/, const mpw */*bvl*/); +MPX_DOBIN(MPX_BITDECL) -extern void mpx_xor(mpw */*dv*/, mpw */*dvl*/, - const mpw */*av*/, const mpw */*avl*/, - const mpw */*bv*/, const mpw */*bvl*/); +/* --- @mpx_[n]and@, @mpx_[n]or@, @mpx_xor@ --- * + * + * Synonyms for the commonly-used functions above. + */ + +#define mpx_and mpx_bit0001 +#define mpx_or mpx_bit0111 +#define mpx_nand mpx_bit1110 +#define mpx_nor mpx_bit1000 +#define mpx_xor mpx_bit0110 + +/* --- @mpx_not@ --- * + * + * Arguments: @mpw *dv, *dvl@ = destination vector + * @const mpw *av, *avl@ = first source vector + * + * Returns: --- + * + * Use; Bitwise NOT. + */ extern void mpx_not(mpw */*dv*/, mpw */*dvl*/, const mpw */*av*/, const mpw */*avl*/); diff --git a/tests/mp b/tests/mp index 79d2980..a73bc65 100644 --- a/tests/mp +++ b/tests/mp @@ -1,6 +1,6 @@ # Test vectors for MP functions # -# $Id: mp,v 1.9 2001/05/07 17:32:23 mdw Exp $ +# $Id: mp,v 1.10 2002/10/06 22:52:50 mdw Exp $ add { 5 4 9; 5 -4 1; -5 4 -1; -5 -4 -9; @@ -21,6 +21,20 @@ div { 9 4 2 1; -9 4 -3 3; 9 -4 -3 -3; -9 -4 2 -1; } +bin2c { + and 5 3 1; + or 5 3 7; + xor 5 3 6; + 1111 0 0 -1; + xor 0x343cd5 -0x6a49c -0x32984f; +} + +lsr2c { + -1 5 -1; + 1 5 0; + -6 2 -2; +} + odd { 1 0 1; 2 1 1; diff --git a/tests/mpx b/tests/mpx index 8507fdc..e8aabac 100644 --- a/tests/mpx +++ b/tests/mpx @@ -1,6 +1,6 @@ # Test vectors for low-level MP functions # -# $Id: mpx,v 1.7 2000/07/15 10:03:13 mdw Exp $ +# $Id: mpx,v 1.8 2002/10/06 22:52:50 mdw Exp $ # --- Load-store tests --- # @@ -20,6 +20,28 @@ load-store { 522f8b1de257972a25ec49c9ff56340e2684e847ef2fa4d5714d7c8d454e90f6; } +# --- Two's complement tests --- + +2cb { + "" ""; + 00 00; + 000000 00000000000000000000; + 01 ff; + 0123456789abcdef fedcba9876543211; + 0123456789abcdef fffffffedcba9876543211; + 0100000000 ffffff00000000; +} + +2cl { + "" ""; + 00 00; + 000000 00000000000000000000; + 01 ff; + efcdab8967452301 1132547698badcfe; + efcdab8967452301 1132547698badcfeffffffff; + 0000000001 00000000ffffffff; +} + # --- Shift tests --- lsl {