From 81578196d5732e443c75768ba9118c581c407cc7 Mon Sep 17 00:00:00 2001 From: mdw Date: Fri, 16 May 2003 09:09:24 +0000 Subject: [PATCH] Fix @mp_lsl2c@. Turns out to be surprisingly tricky. --- mp-arith.c | 29 +++++++++++--- mp.h | 13 ++++++- mpx.c | 129 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- mpx.h | 35 ++++++++++++++++- tests/mp | 17 +++++++- tests/mpx | 88 ++++++++++++++++++++++++++++++++++++++++- 6 files changed, 298 insertions(+), 13 deletions(-) diff --git a/mp-arith.c b/mp-arith.c index 759056b..3d565ae 100644 --- a/mp-arith.c +++ b/mp-arith.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mp-arith.c,v 1.15 2002/10/19 17:56:50 mdw Exp $ + * $Id: mp-arith.c,v 1.16 2003/05/16 09:09:24 mdw Exp $ * * Basic arithmetic on multiprecision integers * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: mp-arith.c,v $ + * Revision 1.16 2003/05/16 09:09:24 mdw + * Fix @mp_lsl2c@. Turns out to be surprisingly tricky. + * * Revision 1.15 2002/10/19 17:56:50 mdw * Fix bit operations. Test them (a bit) better. * @@ -91,13 +94,18 @@ /*----- Main code ---------------------------------------------------------*/ -/* --- @mp_lsl@, @mp_lsr@ --- * +/* --- @mp_lsl@, @mp_lslc@, @mp_lsr@ --- * * * Arguments: @mp *d@ = destination * @mp *a@ = source * @size_t n@ = number of bits to move * * Returns: Result, @a@ shifted left or right by @n@. + * + * Use: Bitwise shift operators. @mp_lslc@ fills the bits introduced + * on the right with ones instead of zeroes: it's used + * internally by @mp_lsl2c@, though it may be useful on its + * own. */ mp *mp_lsl(mp *d, mp *a, size_t n) @@ -109,6 +117,15 @@ mp *mp_lsl(mp *d, mp *a, size_t n) return (d); } +mp *mp_lslc(mp *d, mp *a, size_t n) +{ + MP_DEST(d, MP_LEN(a) + (n + MPW_BITS - 1) / MPW_BITS, a->f); + mpx_lslc(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); @@ -133,7 +150,7 @@ mp *mp_lsl2c(mp *d, mp *a, size_t n) if (!(a->f & MP_NEG)) return (mp_lsl(d, a, n)); d = mp_not2c(d, a); - d = mp_lsl(d, d, n); + d = mp_lslc(d, d, n); d = mp_not2c(d, d); return (d); } @@ -293,10 +310,10 @@ mp *mp_neg(mp *d, mp *a) MP_SHRINK(a); MP_COPY(a); - if (d) MP_DROP(d); - if (a->v == a->vl) { + if (d) + MP_DROP(d); + if (a->v == a->vl) return (a); - } MP_DEST(a, MP_LEN(a), a->f); a->f ^= MP_NEG; return (a); diff --git a/mp.h b/mp.h index bf0303a..c38bb3c 100644 --- a/mp.h +++ b/mp.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mp.h,v 1.16 2002/10/15 22:57:22 mdw Exp $ + * $Id: mp.h,v 1.17 2003/05/16 09:09:24 mdw Exp $ * * Simple multiprecision arithmetic * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: mp.h,v $ + * Revision 1.17 2003/05/16 09:09:24 mdw + * Fix @mp_lsl2c@. Turns out to be surprisingly tricky. + * * Revision 1.16 2002/10/15 22:57:22 mdw * Handy new comparison macros. * @@ -726,16 +729,22 @@ extern int mp_testbit(mp */*x*/, unsigned long /*n*/); extern mp *mp_setbit(mp */*d*/, mp */*x*/, unsigned long /*n*/); extern mp *mp_clearbit(mp */*d*/, mp */*x*/, unsigned long /*n*/); -/* --- @mp_lsl@, @mp_lsr@ --- * +/* --- @mp_lsl@, @mp_lslc@, @mp_lsr@ --- * * * Arguments: @mp *d@ = destination * @mp *a@ = source * @size_t n@ = number of bits to move * * Returns: Result, @a@ shifted left or right by @n@. + * + * Use: Bitwise shift operators. @mp_lslc@ fills the bits introduced + * on the right with ones instead of zeroes: it's used + * internally by @mp_lsl2c@, though it may be useful on its + * own. */ extern mp *mp_lsl(mp */*d*/, mp */*a*/, size_t /*n*/); +extern mp *mp_lslc(mp */*d*/, mp */*a*/, size_t /*n*/); extern mp *mp_lsr(mp */*d*/, mp */*a*/, size_t /*n*/); /* --- @mp_not2c@ --- * diff --git a/mpx.c b/mpx.c index 6375c3e..f40d7d9 100644 --- a/mpx.c +++ b/mpx.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mpx.c,v 1.15 2002/10/20 01:12:31 mdw Exp $ + * $Id: mpx.c,v 1.16 2003/05/16 09:09:24 mdw Exp $ * * Low-level multiprecision arithmetic * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: mpx.c,v $ + * Revision 1.16 2003/05/16 09:09:24 mdw + * Fix @mp_lsl2c@. Turns out to be surprisingly tricky. + * * Revision 1.15 2002/10/20 01:12:31 mdw * Two's complement I/O fixes. * @@ -525,6 +528,104 @@ void mpx_lsl(mpw *dv, mpw *dvl, const mpw *av, const mpw *avl, size_t n) done:; } +/* --- @mpx_lslc@ --- * + * + * Arguments: @mpw *dv, *dvl@ = destination vector base and limit + * @const mpw *av, *avl@ = source vector base and limit + * @size_t n@ = number of bit positions to shift by + * + * Returns: --- + * + * Use: Performs a logical shift left operation on an integer, only + * it fills in the bits with ones instead of zeroes. + */ + +void mpx_lslc(mpw *dv, mpw *dvl, const mpw *av, const mpw *avl, size_t n) +{ + size_t nw; + unsigned nb; + + /* --- Trivial special case --- */ + + if (n == 0) + MPX_COPY(dv, dvl, av, avl); + + /* --- Single bit shifting --- */ + + else if (n == 1) { + mpw w = 1; + while (av < avl) { + mpw t; + if (dv >= dvl) + goto done; + t = *av++; + *dv++ = MPW((t << 1) | w); + w = t >> (MPW_BITS - 1); + } + if (dv >= dvl) + goto done; + *dv++ = MPW(w); + MPX_ZERO(dv, dvl); + goto done; + } + + /* --- Break out word and bit shifts for more sophisticated work --- */ + + nw = n / MPW_BITS; + nb = n % MPW_BITS; + + /* --- Handle a shift by a multiple of the word size --- */ + + if (nb == 0) { + if (nw >= dvl - dv) + MPX_ONE(dv, dvl); + else { + MPX_COPY(dv + nw, dvl, av, avl); + MPX_ONE(dv, dv + nw); + } + } + + /* --- And finally the difficult case --- * + * + * This is a little convoluted, because I have to start from the end and + * work backwards to avoid overwriting the source, if they're both the same + * block of memory. + */ + + else { + mpw w; + size_t nr = MPW_BITS - nb; + size_t dvn = dvl - dv; + size_t avn = avl - av; + + if (dvn <= nw) { + MPX_ONE(dv, dvl); + goto done; + } + + if (dvn > avn + nw) { + size_t off = avn + nw + 1; + MPX_ZERO(dv + off, dvl); + dvl = dv + off; + w = 0; + } else { + avl = av + dvn - nw; + w = *--avl << nb; + } + + while (avl > av) { + mpw t = *--avl; + *--dvl = (t >> nr) | w; + w = t << nb; + } + + *--dvl = (MPW_MAX >> nr) | w; + MPX_ONE(dv, dvl); + } + +done:; +} + /* --- @mpx_lsr@ --- * * * Arguments: @mpw *dv, *dvl@ = destination vector base and limit @@ -1432,6 +1533,31 @@ static int lsl(dstr *v) return (ok); } +static int lslc(dstr *v) +{ + mpw *a, *al; + int n = *(int *)v[1].buf; + mpw *c, *cl; + mpw *d, *dl; + int ok = 1; + + LOAD(a, al, &v[0]); + LOAD(c, cl, &v[2]); + ALLOC(d, dl, al - a + (n + MPW_BITS - 1) / MPW_BITS); + + mpx_lslc(d, dl, a, al, n); + if (!mpx_ueq(d, dl, c, cl)) { + fprintf(stderr, "\n*** lslc(%i) failed\n", n); + dumpmp(" a", a, al); + dumpmp("expected", c, cl); + dumpmp(" result", d, dl); + ok = 0; + } + + free(a); free(c); free(d); + return (ok); +} + static int lsr(dstr *v) { mpw *a, *al; @@ -1600,6 +1726,7 @@ static test_chunk defs[] = { { "2cl", twocl, { &type_hex, &type_hex, } }, { "2cb", twocb, { &type_hex, &type_hex, } }, { "lsl", lsl, { &type_hex, &type_int, &type_hex, 0 } }, + { "lslc", lslc, { &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 } }, { "usub", usub, { &type_hex, &type_hex, &type_hex, 0 } }, diff --git a/mpx.h b/mpx.h index 3364137..bf73912 100644 --- a/mpx.h +++ b/mpx.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mpx.h,v 1.15 2002/10/19 17:56:50 mdw Exp $ + * $Id: mpx.h,v 1.16 2003/05/16 09:09:24 mdw Exp $ * * Low level multiprecision arithmetic * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: mpx.h,v $ + * Revision 1.16 2003/05/16 09:09:24 mdw + * Fix @mp_lsl2c@. Turns out to be surprisingly tricky. + * * Revision 1.15 2002/10/19 17:56:50 mdw * Fix bit operations. Test them (a bit) better. * @@ -217,6 +220,20 @@ memset(_v, 0, MPWS(_vl - _v)); \ } while (0) +/* --- @MPX_ONE@ --- * + * + * Arguments: @v, vl@ = base and limit of vector to clear + * + * Use: Fills the area between the two vector pointers with ones. + */ + +#define MPX_ONE(v, vl) do { \ + mpw * _v = (v); \ + const mpw *_vl = (vl); \ + while (_v < _vl) \ + *_v++ = MPW_MAX; \ +} while (0) + /*----- Loading and storing -----------------------------------------------*/ /* --- @mpx_storel@ --- * @@ -369,6 +386,22 @@ extern void mpx_lsl(mpw */*dv*/, mpw */*dvl*/, const mpw */*av*/, const mpw */*avl*/, size_t /*n*/); +/* --- @mpx_lslc@ --- * + * + * Arguments: @mpw *dv, *dvl@ = destination vector base and limit + * @const mpw *av, *avl@ = source vector base and limit + * @size_t n@ = number of bit positions to shift by + * + * Returns: --- + * + * Use: Performs a logical shift left operation on an integer, only + * it fills in the bits with ones instead of zeroes. + */ + +extern void mpx_lslc(mpw */*dv*/, mpw */*dvl*/, + const mpw */*av*/, const mpw */*avl*/, + size_t /*n*/); + /* --- @mpx_lsr@ --- * * * Arguments: @mpw *dv, *dvl@ = destination vector base and limit diff --git a/tests/mp b/tests/mp index 98399a2..767bd0d 100644 --- a/tests/mp +++ b/tests/mp @@ -1,6 +1,6 @@ # Test vectors for MP functions # -# $Id: mp,v 1.14 2002/10/19 18:55:08 mdw Exp $ +# $Id: mp,v 1.15 2003/05/16 09:09:24 mdw Exp $ add { 5 4 9; 5 -4 1; -5 4 -1; -5 -4 -9; @@ -34,9 +34,22 @@ lsr2c { -1 5 -1; 1 5 0; -6 2 -2; + 5 0 5; + -4 0 -4; 7 2 1; -7 2 -2; - -7 -2 0; + -7 20 -1; +} + +lsl2c { + -1 5 -32; + 5 0 5; + -4 0 -4; + 7 2 28; + -7 2 -28; + 0xc0000000 1 0x180000000; + -0xc0000000 1 -0x180000000; + -1 32 -0x100000000; } setbit { diff --git a/tests/mpx b/tests/mpx index 2dccaef..e54af08 100644 --- a/tests/mpx +++ b/tests/mpx @@ -1,6 +1,6 @@ # Test vectors for low-level MP functions # -# $Id: mpx,v 1.10 2002/10/20 01:12:31 mdw Exp $ +# $Id: mpx,v 1.11 2003/05/16 09:09:24 mdw Exp $ # --- Load-store tests --- # @@ -134,6 +134,92 @@ lsl { 0e0dd2bb4d1e654846356309a2d97fee00000000; } +lslc { + # --- Simple sanity checks --- + + 01 2 07; + 01 4 1f; + + 7 -1 0; + + # --- Copy shifts --- + + 01 0 01; + 0123456789abcdef0123456789abcdef 0 0123456789abcdef0123456789abcdef; + + # --- Single bit shifts --- + + 01 1 03; + ff000000 1 01fe000001; + + # --- Word-size shifts (assumes 32-bit words) --- + + 0123456789abcdef0123456789abcdef 32 + 0123456789abcdef0123456789abcdefffffffff; + + # --- Random tests --- + + 13bbec3a734e0b8b5155600b0826b913 90 + 4eefb0e9cd382e2d4555802c209ae44fffffffffffffffffffffff; + + d6ca6a99fe49b256f80e9643e2bd4f3e 80 + d6ca6a99fe49b256f80e9643e2bd4f3effffffffffffffffffff; + + c94784b40d54de614084915915531ddc 59 + 064a3c25a06aa6f30a04248ac8aa98eee7ffffffffffffff; + + a63c314a39cc37f950b3d530c95ead00 84 + 0a63c314a39cc37f950b3d530c95ead00fffffffffffffffffffff; + + 842d03a339f5004cfd311e2bb23216ac 62 + 210b40e8ce7d40133f4c478aec8c85ab3fffffffffffffff; + + 9a8e659739bf9ee7aa908b7c058c5e7e 123 + 04d4732cb9cdfcf73d54845be02c62f3f7ffffffffffffffffffffffffffffff; + + 287f5774f212db87bcd83a1bbb7b1ad5 6 + 0a1fd5dd3c84b6e1ef360e86eedec6b57f; + + ec1739174d9d4438d3093cf378605a5c 63 + 760b9c8ba6cea21c69849e79bc302d2e7fffffffffffffff; + + 3dfa8ad6a60a783639d05aa5fbfd993d 46 + 0f7ea2b5a9829e0d8e7416a97eff664f7fffffffffff; + + e4e93a80b6d25b34c23aca3a0d06d76c 63 + 72749d405b692d9a611d651d06836bb67fffffffffffffff; + + 5a4cf5becb4b64a1a31637c91b6415fd 102 + 16933d6fb2d2d92868c58df246d9057f7fffffffffffffffffffffffff; + + d92f60928b67416c1e20bd9e09026115 69 + 1b25ec12516ce82d83c417b3c1204c22bfffffffffffffffff; + + eae78f56200d7734f7eb68479fe09d51 18 + 03ab9e3d588035dcd3dfada11e7f827547ffff; + + 4c9c215ead951513d969d66614016f6e 28 + 04c9c215ead951513d969d66614016f6efffffff; + + 5cb1e4d625eac0393644fe6a7e3ff788 33 + b963c9ac4bd580726c89fcd4fc7fef11ffffffff; + + 68b23795968766c77b1897c88a5d6ba8 78 + 1a2c8de565a1d9b1dec625f222975aea3fffffffffffffffffff; + + 3d96cd168c74f9015afb691d629f3f6d 72 + 3d96cd168c74f9015afb691d629f3f6dffffffffffffffffff; + + 38fa8f63dc426399e0f9b5c01231e02c 95 + 1c7d47b1ee2131ccf07cdae00918f0167fffffffffffffffffffffff; + + 90176b493061899ec95677ccc58b8cdf 78 + 2405dad24c186267b2559df33162e337ffffffffffffffffffff; + + 0706e95da68f32a4231ab184d16cbff7 33 + 0e0dd2bb4d1e654846356309a2d97fefffffffff; +} + lsr { # --- Simple sanity checks --- -- 2.11.0