From 5fbe3846b6a2a0eea61ed4ba0ca0c522005d6489 Mon Sep 17 00:00:00 2001 From: mdw Date: Sat, 29 Jul 2000 17:03:31 +0000 Subject: [PATCH] Add support for left-to-right bitscanning, for use in modular exponentiation. --- mp-misc.c | 19 ++++++++++++++++- mp.h | 29 +++++++++++++++++++++++++- mpscan.c | 52 +++++++++++++++++++++++++++++++++++++++++++++-- mpscan.h | 70 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---- 4 files changed, 162 insertions(+), 8 deletions(-) diff --git a/mp-misc.c b/mp-misc.c index 840f947..15c582d 100644 --- a/mp-misc.c +++ b/mp-misc.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mp-misc.c,v 1.2 2000/06/17 11:45:09 mdw Exp $ + * $Id: mp-misc.c,v 1.3 2000/07/29 17:03:31 mdw Exp $ * * Miscellaneous multiprecision support functions * @@ -30,6 +30,10 @@ /*----- Revision history --------------------------------------------------* * * $Log: mp-misc.c,v $ + * Revision 1.3 2000/07/29 17:03:31 mdw + * Add support for left-to-right bitscanning, for use in modular + * exponentiation. + * * Revision 1.2 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 @@ -93,4 +97,17 @@ void mp_minimize(mp *m) void mp_scan(mpscan *sc, const mp *m) { MP_SCAN(sc, m); } +/* --- @mp_scan@ --- * + * + * Arguments: @mpscan *sc@ = pointer to bitscanner block + * @const mp *m@ = pointer to a multiprecision integer + * + * Returns: --- + * + * Use: Initializes a reverse bitscanner on a multiprecision + * integer. + */ + +void mp_rscan(mpscan *sc, const mp *m) { MP_RSCAN(sc, m); } + /*----- That's all, folks -------------------------------------------------*/ diff --git a/mp.h b/mp.h index 12003d0..5bc465d 100644 --- a/mp.h +++ b/mp.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mp.h,v 1.8 2000/06/22 19:02:01 mdw Exp $ + * $Id: mp.h,v 1.9 2000/07/29 17:03:31 mdw Exp $ * * Simple multiprecision arithmetic * @@ -30,6 +30,10 @@ /*----- Revision history --------------------------------------------------* * * $Log: mp.h,v $ + * Revision 1.9 2000/07/29 17:03:31 mdw + * Add support for left-to-right bitscanning, for use in modular + * exponentiation. + * * Revision 1.8 2000/06/22 19:02:01 mdw * Add new functions. * @@ -420,13 +424,36 @@ extern void mp_scan(mpscan */*sc*/, const mp */*m*/); MPSCAN_INITX(_sc, _mm->v, _mm->vl); \ } while (0) +/* --- @mp_rscan@ --- * + * + * Arguments: @mpscan *sc@ = pointer to bitscanner block + * @const mp *m@ = pointer to a multiprecision integer + * + * Returns: --- + * + * Use: Initializes a reverse bitscanner on a multiprecision + * integer. + */ + +extern void mp_rscan(mpscan */*sc*/, const mp */*m*/); + +#define MP_RSCAN(sc, m) do { \ + const mp *_mm = (m); \ + mpscan *_sc = (sc); \ + MPSCAN_RINITX(_sc, _mm->v, _mm->vl); \ +} while (0) + /* --- Other bitscanning aliases --- */ #define mp_step mpscan_step #define mp_bit mpscan_bit +#define mp_rstep mpscan_rstep +#define mp_rbit mpscan_rbit #define MP_STEP MPSCAN_STEP #define MP_BIT MPSCAN_BIT +#define MP_RSTEP MPSCAN_RSTEP +#define MP_RBIT MPSCAN_RBIT /*----- Loading and storing -----------------------------------------------*/ diff --git a/mpscan.c b/mpscan.c index cbfd138..0a5b4f0 100644 --- a/mpscan.c +++ b/mpscan.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mpscan.c,v 1.2 1999/11/13 01:55:10 mdw Exp $ + * $Id: mpscan.c,v 1.3 2000/07/29 17:03:31 mdw Exp $ * * Sequential bit scan of multiprecision integers * @@ -30,6 +30,10 @@ /*----- Revision history --------------------------------------------------* * * $Log: mpscan.c,v $ + * Revision 1.3 2000/07/29 17:03:31 mdw + * Add support for left-to-right bitscanning, for use in modular + * exponentiation. + * * Revision 1.2 1999/11/13 01:55:10 mdw * Fixed so that they compile. Minor interface changes. * @@ -42,7 +46,7 @@ #include "mpscan.h" -/*----- Main code ---------------------------------------------------------*/ +/*----- Right-to-left scanning --------------------------------------------*/ /* --- @mpscan_initx@ --- * * @@ -86,4 +90,48 @@ int mpscan_step(mpscan *m) { return (MPSCAN_STEP(m)); } int mpscan_bit(const mpscan *m) { return (MPSCAN_BIT(m)); } +/*----- Left-to right-scanning --------------------------------------------*/ + +/* --- @mpscan_rinitx@ --- * + * + * Arguments: @mpscan *m@ = pointer to bitscanner structure + * @const mpw *v, *vl@ = vector of words to scan + * + * Returns: --- + * + * Use: Initializes a reverse bitscanner from a low-level + * vector-and-length representation of an integer. Initially no + * bit is ready; you must call @mpscan_rstep@ before anything + * useful will come out. + */ + +void mpscan_rinitx(mpscan *m, const mpw *v, const mpw *vl) +{ + MPSCAN_RINITX(m, v, vl); +} + +/* --- @mpscan_rstep@ --- * + * + * Arguments: @mpscan *m@ = pointer to bitscanner + * + * Returns: Nonzero if there is another bit to read. + * + * Use: Steps on to the next bit in the integer. The macro version + * evaluates its argument multiple times. + */ + +int mpscan_rstep(mpscan *m) { return (MPSCAN_RSTEP(m)); } + +/* --- @mpscan_rbit@ --- * + * + * Arguments: @const mpscan *m@ = pointer to bitscanner + * + * Returns: The value of the current bit. + * + * Use: Reads the value of the current bit looked at by a + * reverse bitscanner. + */ + +int mpscan_rbit(const mpscan *m) { return (MPSCAN_RBIT(m)); } + /*----- That's all, folks -------------------------------------------------*/ diff --git a/mpscan.h b/mpscan.h index 98f2a3d..619681d 100644 --- a/mpscan.h +++ b/mpscan.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mpscan.h,v 1.3 1999/12/10 23:29:48 mdw Exp $ + * $Id: mpscan.h,v 1.4 2000/07/29 17:03:31 mdw Exp $ * * Sequential bit scan of multiprecision integers * @@ -30,6 +30,10 @@ /*----- Revision history --------------------------------------------------* * * $Log: mpscan.h,v $ + * Revision 1.4 2000/07/29 17:03:31 mdw + * Add support for left-to-right bitscanning, for use in modular + * exponentiation. + * * Revision 1.3 1999/12/10 23:29:48 mdw * Change header file guard names. * @@ -62,7 +66,7 @@ typedef struct mpscan { int bits; /* Number of bits left in @w@ */ } mpscan; -/*----- Functions provided ------------------------------------------------*/ +/*----- Right-to-left scanning --------------------------------------------*/ /* --- @mpscan_initx@ --- * * @@ -97,8 +101,7 @@ extern void mpscan_initx(mpscan */*m*/, const mpw */*v*/, const mpw */*vl*/); */ #define MPSCAN_STEP(m) \ - ((m)->bits ? ((m)->w >>= 1, \ - (m)->bits--, 1) : \ + ((m)->bits ? ((m)->w >>= 1, (m)->bits--, 1) : \ (m)->v < (m)->vl ? ((m)->w = *(m)->v++, \ (m)->bits = MPW_BITS - 1, 1) : \ 0) @@ -119,6 +122,65 @@ extern int mpscan_step(mpscan */*m*/); extern int mpscan_bit(const mpscan */*m*/); +/*----- Left-to right-scanning --------------------------------------------*/ + +/* --- @mpscan_rinitx@ --- * + * + * Arguments: @mpscan *m@ = pointer to bitscanner structure + * @const mpw *v, *vl@ = vector of words to scan + * + * Returns: --- + * + * Use: Initializes a reverse bitscanner from a low-level + * vector-and-length representation of an integer. Initially no + * bit is ready; you must call @mpscan_rstep@ before anything + * useful will come out. + */ + +#define MPSCAN_RINITX(m_, v_, vl_) do { \ + mpscan *_m = (m_); \ + _m->v = (v_); \ + _m->vl = (vl_); \ + while (_m->vl > _m->v && !_m->vl[-1]) \ + _m->vl--; \ + _m->bits = 0; \ +} while (0) + +extern void mpscan_rinitx(mpscan */*m*/, + const mpw */*v*/, const mpw */*vl*/); + +/* --- @mpscan_rstep@ --- * + * + * Arguments: @mpscan *m@ = pointer to bitscanner + * + * Returns: Nonzero if there is another bit to read. + * + * Use: Steps on to the next bit in the integer. The macro version + * evaluates its argument multiple times. + */ + +#define MPSCAN_RSTEP(m) \ + ((m)->bits ? ((m)->w <<= 1, (m)->bits--, 1) : \ + (m)->vl > (m)->v ? ((m)->w = *--(m)->vl, \ + (m)->bits = MPW_BITS - 1, 1) : \ + 0) + +extern int mpscan_rstep(mpscan */*m*/); + +/* --- @mpscan_rbit@ --- * + * + * Arguments: @const mpscan *m@ = pointer to bitscanner + * + * Returns: The value of the current bit. + * + * Use: Reads the value of the current bit looked at by a + * reverse bitscanner. + */ + +#define MPSCAN_RBIT(m) (((m)->w >> (MPW_BITS - 1)) & 1) + +extern int mpscan_rbit(const mpscan */*m*/); + /*----- That's all, folks -------------------------------------------------*/ #ifdef __cplusplus -- 2.11.0