libzahls-design.tex - libzahl - big integer library
(HTM) git clone git://git.suckless.org/libzahl
(DIR) Log
(DIR) Files
(DIR) Refs
(DIR) README
(DIR) LICENSE
---
libzahls-design.tex (7474B)
---
1 \chapter{libzahl's design}
2 \label{chap:libzahl's design}
3
4 In this chapter, the design of libzahl is discussed.
5
6 \vspace{1cm}
7 \minitoc
8
9
10 \newpage
11 \section{Memory pool}
12 \label{sec:Memory pool}
13
14 Allocating memory dynamically is an expensive operation.
15 To improve performance, libzahl never deallocates memory
16 before the library is uninitialised, instead it pools
17 memory, that is no longer needed, for reuse.
18
19 Because of the memory pooling, this is a pattern to the
20 allocation sizes. In an allocation, a power of two
21 elements, plus a few elements that are discussed in
22 \secref{sec:Integer structure}, are allocated. That is,
23 the number multiplied by the size of an element.
24 Powers of two (growth factor 2) is not the most memory
25 efficient way to do this, but it is the simplest and
26 performance efficient. This power of two (sans the few
27 extra elements) is used to calculate — getting the index
28 of the only set bit — the index of the bucket in
29 which the allocation is stored when pooled. The buckets
30 are dynamic arrays with the growth factor 1.5. The
31 growth factor 1.5 is often used for dynamic arrays, it
32 is a good compromise between memory usage and performance.
33
34 libzahl also avoids allocating memory by having a set
35 of temporary variables predefined.
36
37
38 \newpage
39 \section{Error handling}
40 \label{sec:Error handling}
41
42 In C, it is traditional to return a sentiel value
43 in case an error has occurred, and set the value
44 of a global variable to describe the error that
45 has occurred. The programmer can choose whether to
46 check for errors, ignore errors where it does not
47 matter, or simple ignore errors altogether and let
48 the program eventually crash. This is a simple
49 technique that gives the programmer a better
50 understanding of what can happen. A great advantage
51 C has over most programming languages.
52
53 Another technique is to use long jumps on error.
54 This technique is not too common, but is has one
55 significant advantage. Error-checks need only be
56 preformed where the error can first be detected.
57 There is no need to check the return value at every
58 function return. This leads to cleaner code, if
59 there are many functions that can raise exceptional
60 conditions, and greater performance under some
61 conditions. This is why this technique is sometimes
62 used in high-performance libraries. libzahl uses
63 this technique.
64
65 Rather than writing
66
67 \begin{alltt}
68 if (zadd(a, b, c))
69 goto out;
70 \end{alltt}
71
72 \noindent
73 or a bit cleaner, if there are a lot of calls,
74
75 \begin{alltt}
76 #define TRY(...) do if (__VA_ARGS__) goto out; while (0)
77 \textcolor{c}{/* \textrm{\ldots} */}
78 TRY(zadd(a, b, c));
79 \end{alltt}
80
81 \noindent
82 we write
83
84 \begin{alltt}
85 jmp_buf env;
86 if (setjmp(env))
87 goto out;
88 zsetup(env);
89 \textcolor{c}{/* \textrm{\ldots} */}
90 zadd(a, b, c);
91 \end{alltt}
92
93 You only need to call {\tt setjmp} and {\tt zsetup}
94 once, but can update the return point by calling
95 them once more.
96
97 If you don't need to check for errors, you can
98 disable error detection at compile-time. By defining
99 the {\tt ZAHL\_UNSAFE} C preprocessor definition
100 when compiling libzahl, and when compiling your
101 software that uses libzahl.
102
103
104 \newpage
105 \section{Integer structure}
106 \label{sec:Integer structure}
107
108 The data type used to represent a big integer with
109 libzahl is {\tt z\_t},\footnote{This name actually
110 violates the naming convention; it should be {\tt Z},
111 or {\tt Zahl} to avoid single-letter names. But this
112 violation is common-place.} defined as
113
114 \begin{alltt}
115 typedef struct zahl z_t[1];
116 \end{alltt}
117
118 \noindent
119 where {\tt struct zahl} is defined as
120
121 \begin{alltt}
122 struct zahl \{
123 int sign; \textcolor{c}{/* \textrm{\emph{not} short for `signum'} */}
124 size_t used;
125 size_t alloced; \textcolor{c}{/* \textrm{short for `allocated'} */}
126 zahl_char_t *chars; \textcolor{c}{/* \textrm{short for `characters'} */}
127 \};
128 \end{alltt}
129
130 \noindent
131 where {\tt zahl\_char\_t} is defined as
132
133 \begin{alltt}
134 typedef uint64_t zahl_char_t;
135 \end{alltt}
136
137 \noindent
138 As a user, try not to think about anything else than
139
140 \begin{alltt}
141 typedef \textcolor{c}{/* \textrm{ignore what is here} */} z_t[1];
142 \end{alltt}
143
144 \noindent
145 details can change in future versions of libzahl.
146
147 {\tt z\_t} is defined as a single-element array. This
148 is often called a reference, or a call-by-reference.
149 There are some flexibility issues with this, why
150 {\tt struct zahl} has beed added, but for most uses
151 with big integers, it makes things simpler. Particularly,
152 you need not work prepend {\tt \&} to variable when making
153 function calls, but the existence of {\tt struct zahl}
154 allows you do so if you so choose.
155
156 The {\tt .sign} member, is either $-1$, 0, or 1,
157 when the integer is negative, zero, or positive,
158 respectively. Whenever {\tt .sign} is 0, the value
159 of {\tt .used} and {\tt .chars} are undefined.
160
161 {\tt .used} holds to the number of elements used in
162 {\tt .chars}, and {\tt .alloced} holds the allocation
163 side of {\tt .chars} measured in elements minus a few
164 extra elements that are always added to the allocation.
165 {\tt .chars} is a little-endian array of 64-bit digits,
166 these 64-bit digits are called `characters' in libzahl.
167 {\tt .chars} holds the absolute value of the
168 represented value.
169
170 Unless {\tt .sign} is 0, {\tt .chars} always contains
171 four extra elements, refered to as fluff. These are
172 merely allocated so functions can assume that they can
173 always manipulate groups of four characters, and need
174 not care about cases where the number of characters is
175 not a multiple of four. There are of course a few cases
176 when the precise number of characters is important.
177
178
179 \newpage
180 \section{Parameters}
181 \label{sec:Parameters}
182
183 The general order of parameters in libzahl functions
184 are: output integers, input integers, input data,
185 output data, parametric values. For example, in
186 addition, the out parameter is the first parameter.
187 But for marshalling and unmarshalling the buffer
188 is last. For random number generation the order is:
189 output, device, distribution, distribution parameters.
190 Whilst the distribution parameters are big integers,
191 they are not considered input integers. The order
192 of the input parameters are that of the order you
193 would write them using mathematical notation, this
194 also holds true if you include the output parameter
195 (as long as there is exactly one output), for example
196
197 \vspace{1em}
198 $a \gets b^c \mod d$
199 \vspace{1em}
200
201 \noindent
202 is written
203
204 \begin{verbatim}
205 zmodpow(a, b, c, d);
206 \end{verbatim}
207
208 \noindent
209 or
210
211 \begin{verbatim}
212 zmodpowu(a, b, c, d);
213 \end{verbatim}
214
215 Like any self respecting bignum library, libzahl
216 supports using the same big integer reference as
217 for output as input, as long as all the output
218 parameters are mutually unique. For example
219
220 \begin{alltt}
221 a += b;
222 \end{alltt}
223
224 \noindent
225 or
226
227 \begin{alltt}
228 a = a + b;
229 \end{alltt}
230
231 \noindent
232 is written, using libzahl, as
233
234 \begin{alltt}
235 zadd(a, a, b);
236 \end{alltt}
237
238 For commutative functions, like {\tt zadd}, the
239 implementation is optimised to assume that this
240 order is more likely to be used than the alternative.
241 That is, we should, for example, write
242
243 \begin{alltt}
244 zadd(a, a, b);
245 \end{alltt}
246
247 \noindent
248 rather than
249
250 \begin{alltt}
251 zadd(a, b, a);
252 \end{alltt}
253
254 \noindent
255 This assumption is not made for non-commutative
256 functions.
257
258 When writting your own functions, be aware,
259 input parameters are generally not declared {\tt const}
260 in libzahl. Currently, some functions actually make
261 modifications (that do not affect the value) to
262 input parameters.