chiark / gitweb /
Merge branch 'mdw/rsvr'
[catacomb] / math / mpscan.h
1 /* -*-c-*-
2  *
3  * Sequential bit scan of multiprecision integers
4  *
5  * (c) 1999 Straylight/Edgeware
6  */
7
8 /*----- Licensing notice --------------------------------------------------*
9  *
10  * This file is part of Catacomb.
11  *
12  * Catacomb is free software; you can redistribute it and/or modify
13  * it under the terms of the GNU Library General Public License as
14  * published by the Free Software Foundation; either version 2 of the
15  * License, or (at your option) any later version.
16  *
17  * Catacomb is distributed in the hope that it will be useful,
18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
20  * GNU Library General Public License for more details.
21  *
22  * You should have received a copy of the GNU Library General Public
23  * License along with Catacomb; if not, write to the Free
24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
25  * MA 02111-1307, USA.
26  */
27
28 #ifndef CATACOMB_MPSCAN_H
29 #define CATACOMB_MPSCAN_H
30
31 #ifdef __cplusplus
32   extern "C" {
33 #endif
34
35 /*----- Header files ------------------------------------------------------*/
36
37 #ifndef CATACOMB_MPW_H
38 #  include "mpw.h"
39 #endif
40
41 /*----- Data structures ---------------------------------------------------*/
42
43 typedef struct mpscan {
44   const mpw *v, *vl;                    /* Vector of words to scan */
45   mpw w;                                /* Current word to scan */
46   int bits;                             /* Number of bits left in @w@ */
47 } mpscan;
48
49 /*----- Right-to-left scanning --------------------------------------------*/
50
51 /* --- @mpscan_initx@ --- *
52  *
53  * Arguments:   @mpscan *m@ = pointer to bitscanner structure
54  *              @const mpw *v, *vl@ = vector of words to scan
55  *
56  * Returns:     ---
57  *
58  * Use:         Initializes a bitscanner from a low-level base-and-limit
59  *              representation of an integer.  Initially no bit is ready; you
60  *              must call @mpscan_step@ before anything useful will come
61  *              out.
62  */
63
64 #define MPSCAN_INITX(m_, v_, vl_) do {                                  \
65   mpscan *_m = (m_);                                                    \
66   _m->v = (v_);                                                         \
67   _m->vl = (vl_);                                                       \
68   _m->bits = 0;                                                         \
69 } while (0)
70
71 extern void mpscan_initx(mpscan */*m*/, const mpw */*v*/, const mpw */*vl*/);
72
73 /* --- @mpscan_step@ --- *
74  *
75  * Arguments:   @mpscan *m@ = pointer to bitscanner
76  *
77  * Returns:     Nonzero if there is another bit to read.
78  *
79  * Use:         Steps on to the next bit in the integer.  The macro version
80  *              evaluates its argument multiple times.
81  */
82
83 #define MPSCAN_STEP(m)                                                  \
84   ((m)->bits ? ((m)->w >>= 1, (m)->bits--, 1) :                         \
85    (m)->v < (m)->vl ? ((m)->w = *(m)->v++,                              \
86                        (m)->bits = MPW_BITS - 1, 1) :                   \
87    0)
88
89 extern int mpscan_step(mpscan */*m*/);
90
91 /* --- @mpscan_bit@ --- *
92  *
93  * Arguments:   @const mpscan *m@ = pointer to bitscanner
94  *
95  * Returns:     The value of the current bit.
96  *
97  * Use:         Reads the value of the current bit looked at by a
98  *              bitscanner.
99  */
100
101 #define MPSCAN_BIT(m) ((m)->w & 1)
102
103 extern int mpscan_bit(const mpscan */*m*/);
104
105 /*----- Left-to right-scanning --------------------------------------------*/
106
107 /* --- @mpscan_rinitx@ --- *
108  *
109  * Arguments:   @mpscan *m@ = pointer to bitscanner structure
110  *              @const mpw *v, *vl@ = vector of words to scan
111  *
112  * Returns:     ---
113  *
114  * Use:         Initializes a reverse bitscanner from a low-level
115  *              vector-and-length representation of an integer.  Initially no
116  *              bit is ready; you must call @mpscan_rstep@ before anything
117  *              useful will come out.
118  */
119
120 #define MPSCAN_RINITX(m_, v_, vl_) do {                                 \
121   mpscan *_m = (m_);                                                    \
122   _m->v = (v_);                                                         \
123   _m->vl = (vl_);                                                       \
124   while (_m->vl > _m->v && !_m->vl[-1])                                 \
125     _m->vl--;                                                           \
126   _m->bits = 0;                                                         \
127 } while (0)
128
129 extern void mpscan_rinitx(mpscan */*m*/,
130                           const mpw */*v*/, const mpw */*vl*/);
131
132 /* --- @mpscan_rstep@ --- *
133  *
134  * Arguments:   @mpscan *m@ = pointer to bitscanner
135  *
136  * Returns:     Nonzero if there is another bit to read.
137  *
138  * Use:         Steps on to the next bit in the integer.  The macro version
139  *              evaluates its argument multiple times.
140  */
141
142 #define MPSCAN_RSTEP(m)                                                 \
143   ((m)->bits ? ((m)->w <<= 1, (m)->bits--, 1) :                         \
144    (m)->vl > (m)->v ? ((m)->w = *--(m)->vl,                             \
145                        (m)->bits = MPW_BITS - 1, 1) :                   \
146    0)
147
148 extern int mpscan_rstep(mpscan */*m*/);
149
150 /* --- @mpscan_rbit@ --- *
151  *
152  * Arguments:   @const mpscan *m@ = pointer to bitscanner
153  *
154  * Returns:     The value of the current bit.
155  *
156  * Use:         Reads the value of the current bit looked at by a
157  *              reverse bitscanner.
158  */
159
160 #define MPSCAN_RBIT(m) (((m)->w >> (MPW_BITS - 1)) & 1)
161
162 extern int mpscan_rbit(const mpscan */*m*/);
163
164 /*----- That's all, folks -------------------------------------------------*/
165
166 #ifdef __cplusplus
167   }
168 #endif
169
170 #endif