/* -*-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
*
/*----- 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.
*
/*----- 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)
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);
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);
}
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);
/* -*-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
*
/*----- 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.
*
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@ --- *
/* -*-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
*
/*----- 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.
*
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
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;
{ "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 } },
/* -*-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
*
/*----- 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.
*
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@ --- *
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
# 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;
-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 {
# 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 ---
#
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 ---
projects / u / mdw / catacomb / commitdiff