[u/mdw/catacomb] / exp.h

/* -*-c-*-
 *
 * $Id: exp.h,v 1.1 2001/06/16 13:00:59 mdw Exp $
 *
 * Generalized exponentiation
 *
 * (c) 2001 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------* 
 *
 * This file is part of Catacomb.
 *
 * Catacomb is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Library General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 * 
 * Catacomb is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Library General Public License for more details.
 * 
 * You should have received a copy of the GNU Library General Public
 * License along with Catacomb; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA.
 */

/*----- Revision history --------------------------------------------------* 
 *
 * $Log: exp.h,v $
 * Revision 1.1  2001/06/16 13:00:59  mdw
 * New generic exponentation code.  Includes sliding-window simultaneous
 * exponentiation.
 *
 */

#ifdef CATACOMB_EXP_H
#  error "Multiple inclusion of <catacomb/exp.h>"
#endif

#define CATACOMB_EXP_H

#ifdef __cplusplus
  extern "C" {
#endif

/*----- Header files ------------------------------------------------------*/

#include <stddef.h>

#include <mLib/alloc.h>

#ifndef CATACOMB_MP_H
#  include "mp.h"
#endif

/*----- Data structures ---------------------------------------------------*/

typedef struct exp_simulscan {
  mpw w;
  size_t len;
  const mpw *v;
} exp_simulscan;  

typedef struct exp_simul {
  unsigned b;
  size_t o, n;
  exp_simulscan *s;
} exp_simul;

/*----- Macros provided ---------------------------------------------------*/

/* --- Parameters --- */

#ifndef EXP_WINSZ			/* Sliding window size */
#  define EXP_WINSZ 4			/* Predefine if you need to */
#endif

/* --- These are determined from the window size --- */

#define EXP_TABSZ (1 << EXP_WINSZ)
#define EXP_THRESH (((MPW_BITS / EXP_WINSZ) << 2) + 1)

/* --- Required operations --- *
 *
 * The macros here are independent of the underlying group elements.  You
 * must provide the necessary group operations and other definitions.  The
 * group operation is assumed to be written multiplicatively.
 *
 * @EXP_TYPE@			The type of a group element, e.g., @mp *@.
 *
 * @EXP_COPY(d, x)@		Makes @d@ be a copy of @x@.
 *
 * @EXP_DROP(x)@		Discards the element @x@, reclaiming any
 *				memory it used.
 *
 * @EXP_MUL(a, x)@		Multiplies @a@ by @x@ (writing the result
 *				back to @a@).
 *
 * @EXP_SQR(a)@			Multiplies @a@ by itself.
 *
 * @EXP_SETMUL(d, x, y)@	Sets @d@ to be the product of @x@ and @y@.
 *				The value @d@ has not been initialized.
 *
 * @EXP_SETSQR(d, x)@		Sets @d@ to be the square of @x@.
 *
 * Only @EXP_TYPE@, @EXP_MUL@ and @EXP_SQR@ are required for simple
 * exponentation.  Sliding window and simultaneous exponentation require all
 * of the operations.
 */

#ifndef EXP_TYPE
#  error "EXP_TYPE not defined for <catacomb/exp.h>"
#endif

/* --- @EXP_SIMPLE@ --- *
 *
 * Arguments:	@a@ = the result object, initially a multiplicative identity
 *		@g@ = the object to exponentiate
 *		@x@ = the exponent, as a multiprecision integer
 *
 * Use:		Performs a simple left-to-right exponentiation.  At the end
 *		of the code, the answer is left in @a@; @g@ and @x@ are
 *		unchanged.
 */

#define EXP_SIMPLE(a, g, x) do {					\
  mpscan sc;								\
  unsigned sq = 0;							\
									\
  /* --- Begin scanning --- */						\
									\
  mp_rscan(&sc, x);							\
  if (!MP_RSTEP(&sc))							\
    goto exp_simple_exit;						\
  while (!MP_RBIT(&sc))							\
    MP_RSTEP(&sc);							\
									\
  /* --- Do the main body of the work --- */				\
									\
  for (;;) {								\
    EXP_MUL(a, g);							\
    sq = 0;								\
    for (;;) {								\
      if (!MP_RSTEP(&sc))						\
	goto exp_simple_done;						\
      sq++;								\
      if (MP_RBIT(&sc))							\
	break;								\
    }									\
    while (sq--) EXP_SQR(a);						\
  }									\
									\
  /* --- Do a final round of squaring --- */				\
									\
exp_simple_done:							\
  while (sq--) EXP_SQR(a);						\
exp_simple_exit:;							\
} while (0)

/* --- @EXP_WINDOW@ --- *
 *
 * Arguments:	@a@ = the result object, initially a multiplicative identity
 *		@g@ = the object to exponentiate
 *		@x@ = the exponent, as a multiprecision integer
 *
 * Use:		Performs a sliding-window exponentiation.  At the end of the
 *		code, the answer is left in @a@; @g@ and @x@ are unchanged.
 */

#define EXP_WINDOW(a, g, x) do {					\
  EXP_TYPE *v;								\
  EXP_TYPE g2;								\
  unsigned i, sq = 0;							\
  mpscan sc;								\
									\
  /* --- Get going --- */						\
									\
  mp_rscan(&sc, x);							\
  if (!MP_RSTEP(&sc))							\
    goto exp_window_exit;						\
									\
  /* --- Do the precomputation --- */					\
									\
  EXP_SETSQR(g2, g);							\
  v = xmalloc(EXP_TABSZ * sizeof(EXP_TYPE));				\
  EXP_COPY(v[0], g);							\
  for (i = 1; i < EXP_TABSZ; i++)					\
    EXP_SETMUL(v[i], v[i - 1], g2);					\
  EXP_DROP(g2);								\
									\
  /* --- Skip top-end zero bits --- *					\
   *									\
   * If the initial step worked, there must be a set bit somewhere, so	\
   * keep stepping until I find it.					\
   */									\
									\
  while (!MP_RBIT(&sc))							\
    MP_RSTEP(&sc);							\
									\
  /* --- Now for the main work --- */					\
									\
  for (;;) {								\
    unsigned l = 1;							\
    unsigned z = 0;							\
									\
    /* --- The next bit is set, so read a window index --- *		\
     *									\
     * Reset @i@ to zero and increment @sq@.  Then, until either I read	\
     * @WINSZ@ bits or I run out of bits, scan in a bit: if it's clear,	\
     * bump the @z@ counter; if it's set, push a set bit into @i@,	\
     * shift it over by @z@ bits, bump @sq@ by @z + 1@ and clear @z@.	\
     * By the end of this palaver, @i@ is an index to the precomputed	\
     * value in @v@.							\
     */									\
									\
    i = 0;								\
    sq++;								\
    while (l < EXP_WINSZ && MP_RSTEP(&sc)) {				\
      l++;								\
      if (!MP_RBIT(&sc))						\
	z++;								\
      else {								\
	i = ((i << 1) | 1) << z;					\
	sq += z + 1;							\
	z = 0;								\
      }									\
    }									\
									\
    /* --- Do the squaring --- *					\
     *									\
     * Remember that @sq@ carries over from the zero-skipping stuff	\
     * below.								\
     */									\
									\
    while (sq--) EXP_SQR(a);						\
									\
    /* --- Do the multiply --- */					\
									\
    EXP_MUL(a, v[i]);							\
									\
    /* --- Now grind along through the rest of the bits --- */		\
									\
    sq = z;								\
    for (;;) {								\
      if (!MP_RSTEP(&sc))						\
	goto exp_window_done;						\
      if (MP_RBIT(&sc))							\
	break;								\
      sq++;								\
    }									\
  }									\
									\
  /* --- Do a final round of squaring --- */				\
									\
exp_window_done:							\
  while (sq--) EXP_SQR(a);						\
  for (i = 0; i < EXP_TABSZ; i++)					\
    EXP_DROP(v[i]);							\
  xfree(v);								\
exp_window_exit:;							\
} while (0)

/* --- @EXP_SIMUL@ --- *
 *
 * Arguments:	@a@ = the result object, initially a multiplicative identity
 *		@f@ = pointer to a vector of base/exp pairs
 *		@n@ = the number of base/exp pairs
 *
 * Use:		Performs a simultaneous sliding-window exponentiation.  The
 *		@f@ table is an array of structures containing members @base@
 *		of type @EXP_TYPE@, and @exp@ of type @mp *@.
 */

#define EXP_SIMUL(a, f, n) do {						\
  size_t i, j, jj, k;							\
  size_t vn = 1 << (EXP_WINSZ * n), m = (1 << n) - 1;			\
  EXP_TYPE *v = xmalloc(vn * sizeof(EXP_TYPE));				\
  exp_simul e;								\
  unsigned sq = 0;							\
									\
  /* --- Fill in the precomputed table --- */				\
									\
  j = 1;								\
  for (i = 0; i < n; i++) {						\
    EXP_COPY(v[j], f[n - 1 - i].base);					\
    j <<= 1;								\
  }									\
  k = n * EXP_WINSZ;							\
  jj = 1;								\
  for (; i < k; i++) {							\
    EXP_SETSQR(v[j], v[jj]);						\
    j <<= 1; jj <<= 1;							\
  }									\
  for (i = 1; i < vn; i <<= 1) {					\
    for (j = 1; j < i; j++)						\
      EXP_SETMUL(v[j + i], v[j], v[i]);					\
  }									\
									\
  /* --- Set up the bitscanners --- *					\
   *									\
   * Got to use custom scanners, to keep them all in sync.		\
   */									\
									\
  e.n = n;								\
  e.b = 0;								\
  e.s = xmalloc(n * sizeof(*e.s));					\
  e.o = 0;								\
  for (i = 0; i < n; i++) {						\
    MP_SHRINK(f[i].exp);						\
    e.s[i].len = MP_LEN(f[i].exp);					\
    e.s[i].v = f[i].exp->v;						\
    if (e.s[i].len > e.o)						\
      e.o = e.s[i].len;							\
  }									\
									\
  /* --- Skip as far as a nonzero column in the exponent matrix --- */	\
									\
  do {									\
    if (!e.o && !e.b)							\
      goto exp_simul_done;						\
    i = exp_simulnext(&e, 0);						\
  } while (!(i & m));							\
									\
  /* --- Now for the main work --- */					\
									\
  for (;;) {								\
    unsigned l = 1;							\
    unsigned z = 0;							\
									\
    /* --- Just read a nonzero column, so read a window index --- *	\
     *									\
     * Clear high bits of @i@ and increment @sq@.  Then, until either I	\
     * read @WINSZ@ columns or I run out, scan in a column and append	\
     * it to @i@.  If it's zero, bump the @z@ counter; if it's nonzero,	\
     * bump @sq@ by @z + 1@ and clear @z@.  By the end of this palaver,	\
     * @i@ is an index to the precomputed value in @v@, followed by	\
     * @n * z@ zero bits.						\
     */									\
									\
    sq++;								\
    while (l < EXP_WINSZ && (e.o || e.b)) {				\
      l++;								\
      i = exp_simulnext(&e, i);						\
      if (!(i & m))							\
	z++;								\
      else {								\
	sq += z + 1;							\
	z = 0;								\
      }									\
    }									\
									\
    /* --- Do the squaring --- *					\
     *									\
     * Remember that @sq@ carries over from the zero-skipping stuff	\
     * below.								\
     */									\
									\
    while (sq--) EXP_SQR(a);						\
									\
    /* --- Do the multiply --- */					\
									\
    i >>= (z * n);							\
    EXP_MUL(a, v[i]);							\
									\
    /* --- Now grind along through the rest of the bits --- */		\
									\
    sq = z;								\
    for (;;) {								\
      if (!e.o && !e.b)							\
	goto exp_simul_done;						\
      if ((i = exp_simulnext(&e, 0)) != 0)				\
	break;								\
      sq++;								\
    }									\
  }									\
									\
  /* --- Do a final round of squaring --- */				\
									\
exp_simul_done:								\
  while (sq--) EXP_SQR(a);						\
  for (i = 1; i < vn; i++)					\
    EXP_DROP(v[i]);							\
  xfree(v);								\
} while (0)

/*----- Functions provided ------------------------------------------------*/

/* --- @exp_simulnext@ --- *
 *
 * Arguments:	@exp_simul *e@ = pointer to state structure
 *		@size_t x@ = a current accumulator
 *
 * Returns:	The next column of bits.
 *
 * Use:		Scans the next column of bits for a simultaneous
 *		exponentiation.
 */

extern size_t exp_simulnext(exp_simul */*e*/, size_t /*x*/);

/*----- That's all, folks -------------------------------------------------*/

#ifdef __cplusplus
  }
#endif
Commit	Line	Data
7765e926	1	/* --c--
	2	*
	3	* $Id: exp.h,v 1.1 2001/06/16 13:00:59 mdw Exp $
	4	*
	5	* Generalized exponentiation
	6	*
	7	* (c) 2001 Straylight/Edgeware
	8	*/
	9
	10	/----- Licensing notice --------------------------------------------------
	11	*
	12	* This file is part of Catacomb.
	13	*
	14	* Catacomb is free software; you can redistribute it and/or modify
	15	* it under the terms of the GNU Library General Public License as
	16	* published by the Free Software Foundation; either version 2 of the
	17	* License, or (at your option) any later version.
	18	*
	19	* Catacomb is distributed in the hope that it will be useful,
	20	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	21	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	22	* GNU Library General Public License for more details.
	23	*
	24	* You should have received a copy of the GNU Library General Public
	25	* License along with Catacomb; if not, write to the Free
	26	* Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
	27	* MA 02111-1307, USA.
	28	*/
	29
	30	/----- Revision history --------------------------------------------------
	31	*
	32	* $Log: exp.h,v $
	33	* Revision 1.1 2001/06/16 13:00:59 mdw
	34	* New generic exponentation code. Includes sliding-window simultaneous
	35	* exponentiation.
	36	*
	37	*/
	38
	39	#ifdef CATACOMB_EXP_H
	40	# error "Multiple inclusion of <catacomb/exp.h>"
	41	#endif
	42
	43	#define CATACOMB_EXP_H
	44
	45	#ifdef __cplusplus
	46	extern "C" {
	47	#endif
	48
	49	/----- Header files ------------------------------------------------------/
	50
	51	#include <stddef.h>
	52
	53	#include <mLib/alloc.h>
	54
	55	#ifndef CATACOMB_MP_H
	56	# include "mp.h"
	57	#endif
	58
	59	/----- Data structures ---------------------------------------------------/
	60
	61	typedef struct exp_simulscan {
	62	mpw w;
	63	size_t len;
	64	const mpw *v;
65	} exp_simulscan;
66
67	typedef struct exp_simul {
68	unsigned b;
69	size_t o, n;
70	exp_simulscan *s;
71	} exp_simul;
72
73	/----- Macros provided ---------------------------------------------------/
74
75	/* --- Parameters --- */
76
77	#ifndef EXP_WINSZ /* Sliding window size */
78	# define EXP_WINSZ 4 /* Predefine if you need to */
79	#endif
80
81	/* --- These are determined from the window size --- */
82
83	#define EXP_TABSZ (1 << EXP_WINSZ)
84	#define EXP_THRESH (((MPW_BITS / EXP_WINSZ) << 2) + 1)
85
86	/* --- Required operations --- *
87	*
88	* The macros here are independent of the underlying group elements. You
89	* must provide the necessary group operations and other definitions. The
90	* group operation is assumed to be written multiplicatively.
91	*
92	* @EXP_TYPE@ The type of a group element, e.g., @mp *@.
93	*
94	* @EXP_COPY(d, x)@ Makes @d@ be a copy of @x@.
95	*
96	* @EXP_DROP(x)@ Discards the element @x@, reclaiming any
97	* memory it used.
98	*
99	* @EXP_MUL(a, x)@ Multiplies @a@ by @x@ (writing the result
100	* back to @a@).
101	*
102	* @EXP_SQR(a)@ Multiplies @a@ by itself.
103	*
104	* @EXP_SETMUL(d, x, y)@ Sets @d@ to be the product of @x@ and @y@.
105	* The value @d@ has not been initialized.
106	*
107	* @EXP_SETSQR(d, x)@ Sets @d@ to be the square of @x@.
108	*
109	* Only @EXP_TYPE@, @EXP_MUL@ and @EXP_SQR@ are required for simple
110	* exponentation. Sliding window and simultaneous exponentation require all
111	* of the operations.
112	*/
113
114	#ifndef EXP_TYPE
115	# error "EXP_TYPE not defined for <catacomb/exp.h>"
116	#endif
117
118	/* --- @EXP_SIMPLE@ --- *
119	*
120	* Arguments: @a@ = the result object, initially a multiplicative identity
121	* @g@ = the object to exponentiate
122	* @x@ = the exponent, as a multiprecision integer
123	*
124	* Use: Performs a simple left-to-right exponentiation. At the end
125	* of the code, the answer is left in @a@; @g@ and @x@ are
126	* unchanged.
127	*/
128
129	#define EXP_SIMPLE(a, g, x) do { \
130	mpscan sc; \
131	unsigned sq = 0; \
132	\
133	/* --- Begin scanning --- */ \
134	\
135	mp_rscan(&sc, x); \
136	if (!MP_RSTEP(&sc)) \
137	goto exp_simple_exit; \
138	while (!MP_RBIT(&sc)) \
139	MP_RSTEP(&sc); \
140	\
141	/* --- Do the main body of the work --- */ \
142	\
143	for (;;) { \
144	EXP_MUL(a, g); \
145	sq = 0; \
146	for (;;) { \
147	if (!MP_RSTEP(&sc)) \
148	goto exp_simple_done; \
149	sq++; \
150	if (MP_RBIT(&sc)) \
151	break; \
152	} \
153	while (sq--) EXP_SQR(a); \
154	} \
155	\
156	/* --- Do a final round of squaring --- */ \
157	\
158	exp_simple_done: \
159	while (sq--) EXP_SQR(a); \
160	exp_simple_exit:; \
161	} while (0)
162
163	/* --- @EXP_WINDOW@ --- *
164	*
165	* Arguments: @a@ = the result object, initially a multiplicative identity
166	* @g@ = the object to exponentiate
167	* @x@ = the exponent, as a multiprecision integer
168	*
169	* Use: Performs a sliding-window exponentiation. At the end of the
170	* code, the answer is left in @a@; @g@ and @x@ are unchanged.
171	*/
172
173	#define EXP_WINDOW(a, g, x) do { \
174	EXP_TYPE *v; \
175	EXP_TYPE g2; \
176	unsigned i, sq = 0; \
177	mpscan sc; \
178	\
179	/* --- Get going --- */ \
180	\
181	mp_rscan(&sc, x); \
182	if (!MP_RSTEP(&sc)) \
183	goto exp_window_exit; \
184	\
185	/* --- Do the precomputation --- */ \
186	\
187	EXP_SETSQR(g2, g); \
188	v = xmalloc(EXP_TABSZ * sizeof(EXP_TYPE)); \
189	EXP_COPY(v[0], g); \
190	for (i = 1; i < EXP_TABSZ; i++) \
191	EXP_SETMUL(v[i], v[i - 1], g2); \
192	EXP_DROP(g2); \
193	\
194	/* --- Skip top-end zero bits --- * \
195	* \
196	* If the initial step worked, there must be a set bit somewhere, so \
197	* keep stepping until I find it. \
198	*/ \
199	\
200	while (!MP_RBIT(&sc)) \
201	MP_RSTEP(&sc); \
202	\
203	/* --- Now for the main work --- */ \
204	\
205	for (;;) { \
206	unsigned l = 1; \
207	unsigned z = 0; \
208	\
209	/* --- The next bit is set, so read a window index --- * \
210	* \
211	* Reset @i@ to zero and increment @sq@. Then, until either I read \
212	* @WINSZ@ bits or I run out of bits, scan in a bit: if it's clear, \
213	* bump the @z@ counter; if it's set, push a set bit into @i@, \
214	* shift it over by @z@ bits, bump @sq@ by @z + 1@ and clear @z@. \
215	* By the end of this palaver, @i@ is an index to the precomputed \
216	* value in @v@. \
217	*/ \
218	\
219	i = 0; \
220	sq++; \
221	while (l < EXP_WINSZ && MP_RSTEP(&sc)) { \
222	l++; \
223	if (!MP_RBIT(&sc)) \
224	z++; \
225	else { \
226	i = ((i << 1) \| 1) << z; \
227	sq += z + 1; \
228	z = 0; \
229	} \
230	} \
231	\
232	/* --- Do the squaring --- * \
233	* \
234	* Remember that @sq@ carries over from the zero-skipping stuff \
235	* below. \
236	*/ \
237	\
238	while (sq--) EXP_SQR(a); \
239	\
240	/* --- Do the multiply --- */ \
241	\
242	EXP_MUL(a, v[i]); \
243	\
244	/* --- Now grind along through the rest of the bits --- */ \
245	\
246	sq = z; \
247	for (;;) { \
248	if (!MP_RSTEP(&sc)) \
249	goto exp_window_done; \
250	if (MP_RBIT(&sc)) \
251	break; \
252	sq++; \
253	} \
254	} \
255	\
256	/* --- Do a final round of squaring --- */ \
257	\
258	exp_window_done: \
259	while (sq--) EXP_SQR(a); \
260	for (i = 0; i < EXP_TABSZ; i++) \
261	EXP_DROP(v[i]); \
262	xfree(v); \
263	exp_window_exit:; \
264	} while (0)
265
266	/* --- @EXP_SIMUL@ --- *
267	*
268	* Arguments: @a@ = the result object, initially a multiplicative identity
269	* @f@ = pointer to a vector of base/exp pairs
270	* @n@ = the number of base/exp pairs
271	*
272	* Use: Performs a simultaneous sliding-window exponentiation. The
273	* @f@ table is an array of structures containing members @base@
274	* of type @EXP_TYPE@, and @exp@ of type @mp *@.
275	*/
276
277	#define EXP_SIMUL(a, f, n) do { \
278	size_t i, j, jj, k; \
279	size_t vn = 1 << (EXP_WINSZ * n), m = (1 << n) - 1; \
280	EXP_TYPE v = xmalloc(vn sizeof(EXP_TYPE)); \
281	exp_simul e; \
282	unsigned sq = 0; \
283	\
284	/* --- Fill in the precomputed table --- */ \
285	\
286	j = 1; \
287	for (i = 0; i < n; i++) { \
288	EXP_COPY(v[j], f[n - 1 - i].base); \
289	j <<= 1; \
290	} \
291	k = n * EXP_WINSZ; \
292	jj = 1; \
293	for (; i < k; i++) { \
294	EXP_SETSQR(v[j], v[jj]); \
295	j <<= 1; jj <<= 1; \
296	} \
297	for (i = 1; i < vn; i <<= 1) { \
298	for (j = 1; j < i; j++) \
299	EXP_SETMUL(v[j + i], v[j], v[i]); \
300	} \
301	\
302	/* --- Set up the bitscanners --- * \
303	* \
304	* Got to use custom scanners, to keep them all in sync. \
305	*/ \
306	\
307	e.n = n; \
308	e.b = 0; \
309	e.s = xmalloc(n * sizeof(*e.s)); \
310	e.o = 0; \
311	for (i = 0; i < n; i++) { \
312	MP_SHRINK(f[i].exp); \
313	e.s[i].len = MP_LEN(f[i].exp); \
314	e.s[i].v = f[i].exp->v; \
315	if (e.s[i].len > e.o) \
316	e.o = e.s[i].len; \
317	} \
318	\
319	/* --- Skip as far as a nonzero column in the exponent matrix --- */ \
320	\
321	do { \
322	if (!e.o && !e.b) \
323	goto exp_simul_done; \
324	i = exp_simulnext(&e, 0); \
325	} while (!(i & m)); \
326	\
327	/* --- Now for the main work --- */ \
328	\
329	for (;;) { \
330	unsigned l = 1; \
331	unsigned z = 0; \
332	\
333	/* --- Just read a nonzero column, so read a window index --- * \
334	* \
335	* Clear high bits of @i@ and increment @sq@. Then, until either I \
336	* read @WINSZ@ columns or I run out, scan in a column and append \
337	* it to @i@. If it's zero, bump the @z@ counter; if it's nonzero, \
338	* bump @sq@ by @z + 1@ and clear @z@. By the end of this palaver, \
339	* @i@ is an index to the precomputed value in @v@, followed by \
340	* @n * z@ zero bits. \
341	*/ \
342	\
343	sq++; \
344	while (l < EXP_WINSZ && (e.o \|\| e.b)) { \
345	l++; \
346	i = exp_simulnext(&e, i); \
347	if (!(i & m)) \
348	z++; \
349	else { \
350	sq += z + 1; \
351	z = 0; \
352	} \
353	} \
354	\
355	/* --- Do the squaring --- * \
356	* \
357	* Remember that @sq@ carries over from the zero-skipping stuff \
358	* below. \
359	*/ \
360	\
361	while (sq--) EXP_SQR(a); \
362	\
363	/* --- Do the multiply --- */ \
364	\
365	i >>= (z * n); \
366	EXP_MUL(a, v[i]); \
367	\
368	/* --- Now grind along through the rest of the bits --- */ \
369	\
370	sq = z; \
371	for (;;) { \
372	if (!e.o && !e.b) \
373	goto exp_simul_done; \
374	if ((i = exp_simulnext(&e, 0)) != 0) \
375	break; \
376	sq++; \
377	} \
378	} \
379	\
380	/* --- Do a final round of squaring --- */ \
381	\
382	exp_simul_done: \
383	while (sq--) EXP_SQR(a); \
384	for (i = 1; i < vn; i++) \
385	EXP_DROP(v[i]); \
386	xfree(v); \
387	} while (0)
388
389	/----- Functions provided ------------------------------------------------/
390
391	/* --- @exp_simulnext@ --- *
392	*
393	* Arguments: @exp_simul *e@ = pointer to state structure
394	* @size_t x@ = a current accumulator
395	*
396	* Returns: The next column of bits.
397	*
398	* Use: Scans the next column of bits for a simultaneous
399	* exponentiation.
400	*/
401
402	extern size_t exp_simulnext(exp_simul /e/, size_t /x*/);
403
404	/----- That's all, folks -------------------------------------------------/
405
406	#ifdef __cplusplus
407	}
408	#endif