what-is-libzahl.tex - libzahl - big integer library
HTML git clone git://git.suckless.org/libzahl
DIR Log
DIR Files
DIR Refs
DIR README
DIR LICENSE
---
what-is-libzahl.tex (8419B)
---
1 \chapter{What is libzahl?}
2 \label{chap:What is libzahl?}
3
4 In this chapter, it is discussed what libzahl is,
5 why it is called libzahl, why it exists, why
6 you should use it, what makes it different, and
7 what is its limitations.
8
9 \vspace{1cm}
10 \minitoc
11
12
13 \newpage
14 \section{The name and the what}
15 \label{sec:The name and the what}
16
17 In mathematics, the set of all integers is represented
18 by a bold uppercase `Z' ({\bf Z}), or sometimes % proper symbol
19 double-stroked (blackboard bold) ($\mathbb{Z}$). This symbol % hand-written style, specially on whiteboards and blackboards
20 is derived from the german word for integers: `Zahlen'
21 [\textprimstress{}tsa\textlengthmark{}l\textschwa{}n],
22 whose singular is `Zahl' [tsa\textlengthmark{}l]. libzahl
23 [l\textsecstress{}\textsci{}b\textprimstress{}tsa\textlengthmark{}l]
24 is a C library capable of representing very large integers,
25 limited by the memory address space and available memory.
26 Whilst this is almost none of the elements in {\bf Z},
27 it is substantially more than available using the intrinsic
28 integer types in C. libzahl of course also implements
29 functions for performing arithmetic operations over
30 integers represented using libzahl. Libraries such as
31 libzahl are called bigint libraries, big integer libraries,
32 multiple precision integer libraries, arbitrary precision
33 integer libraries,\footnote{`Multiple precision integer'
34 and `arbitrary precision integer' are misnomers, precision
35 is only relevant for floating-point numbers.} or bignum
36 libraries, or any of the previous with `number' substituted
37 for `integer'. Some libraries that refer to themselves as bignum
38 libraries or any of using the word `number' support other
39 number types than integers. libzahl only supports integers.
40
41
42 \newpage
43 \section{Why does it exist?}
44 \label{sec:Why does it exist?}
45
46 libzahl's main competitors are GNU MP (gmp),\footnote{GNU
47 Multiple Precision Arithmetic Library} LibTomMath (ltm),
48 TomsFastMath (tfm) and Hebimath. All of these have problems:
49
50 \begin{itemize}
51 \item
52 GNU MP is extremely bloated, can only be complied with
53 GCC, and requires that you use glibc unless another C
54 standard library was used when GNU MP was compiled.
55 Additionally, whilst its performance is generally good,
56 it can still be improved. Furthermore, GNU MP cannot be
57 used for robust applications.
58
59 \item
60 LibTomMath is very slow, in fact performance is not its
61 priority, rather its simplicity is the priority. Despite
62 this, it is not really that simple.
63
64 \item
65 TomsFastMath is slow, complicated, and is not a true
66 big integer library and is specifically targeted at
67 cryptography.
68 \end{itemize}
69
70 libzahl is developed under the suckless.org umbrella.
71 As such, it attempts to follow the suckless
72 philosophy.\footnote{\href{http://suckless.org/philosophy}
73 {http://suckless.org/philosophy}} libzahl is simple,
74 very fast, simple to use, and can be used in robust
75 applications. Currently however, it does not support
76 multithreading, but it has better support for multiprocessing
77 and distributed computing than its competitors.
78
79 Lesser ``competitors'' (less known) to libzahl include
80 Hebimath and bsdnt.
81
82 \begin{itemize}
83 \item
84 Hebimath is far from stable, some fundamental functions
85 are not implemented and some functions are broken. The
86 author of libzahl thinks Hebimath is promising, but that
87 it could be better designed. Like libzahl, Hebimath aims
88 to follow the suckless philosophy.
89
90 \item
91 bsdnt has not been thoroughly investigated, but it
92 does not look promising.
93 \end{itemize}
94
95
96 \newpage
97 \section{How is it different?}
98 \label{sec:How is it different?}
99
100 All big number libraries have in common that both input
101 and output integers are parameters for the functions.
102 There are however two variants of this: input parameters
103 followed by output parameters, and output parameters
104 followed by input parameters. The former variant is the
105 conventional for C functions. The latter is more in style
106 with primitive operations, pseudo-code, mathematics, and
107 how it would look if the output was return. In libzahl, the
108 latter convention is used. That is, we write
109
110 \begin{alltt}
111 zadd(sum, augend, addend);
112 \end{alltt}
113
114 \noindent
115 rather than
116
117 \begin{alltt}
118 zadd(augend, addend, sum);
119 \end{alltt}
120
121 \noindent
122 This can be compared to
123
124 \vspace{1em}
125 $sum \gets augend + addend$
126 \vspace{1em}
127
128 \noindent
129 versus
130
131 \vspace{1em}
132 $augend + addend \rightarrow sum$.
133 \vspace{1em}
134
135 libzahl, GNU MP, and Hebimath use the output-first
136 convention.\footnote{GNU MP-style.} LibTomMath and
137 TomsFastMath use the input-first convention.\footnote{BSD
138 MP-style.}
139
140 Unlike other bignum libraries, errors in libzahl are
141 caught using {\tt setjmp}. This ensure that it can be
142 used in robust applications, catching errors does not
143 become a mess, and it minimises the overhead of
144 catching errors. Typically, errors can be checked when
145 they can occur and after each function return; however,
146 here they can be checked only when they can occur.
147
148 Additionally, libzahl tries to keep the functions'
149 names simple and natural rather than technical or
150 mathematical. The names resemble those of the standard
151 integer operators. For example, the left-shift, right-shift
152 and truncation bit-operations in libzahl are called
153 {\tt zlsh}, {\tt zrsh} and {\tt ztrunc}, respectively.
154 In GNU MP, they are called {\tt mpz\_mul\_2exp},
155 {\tt mpz\_tdiv\_q\_2exp} and {\tt mpz\_tdiv\_r\_2exp}.
156 The need of complicated names are diminished by resisting
157 to implement all possible variants of each operations.
158 Variants of a function simply append a short description
159 of the difference in plain text. For example, a variant of
160 {\tt zadd} that makes the assumption that both operands
161 are non-negative (or if not so, calculates the sum of
162 their absolute values) is called {\tt zadd\_unsigned}.
163 If libzahl would have had floored and ceiled variants of
164 {\tt zdiv} (truncated division), they would have been
165 called {\tt zdiv\_floor} and {\tt zdiv\_ceiling}.
166 {\tt zdiv} and {\tt zmod} (modulus) are variants of
167 {\tt zdivmod} that throw away one of the outputs. These
168 names can be compared to GNU MP's variants of truncated
169 division: {\tt mpz\_tdiv\_q}, {\tt mpz\_tdiv\_r} and
170 {\tt mpz\_tdiv\_qr}.
171
172
173 \newpage
174 \section{Limitations}
175 \label{sec:Limitations}
176
177 libzahl is not recommended for cryptographic
178 applications, it is not mature enough, and its
179 author does not have the necessary expertise.
180 And in particular, it does not implement constant
181 time operations, and it does not clear pooled
182 memory. Using libzahl in cryptographic application
183 is insecure; your application may become susceptible
184 attacks such as timing attacks, power-monitoring
185 attacks, electromagnetic attacks, acoustic
186 cryptanalysis, and data remanence attacks. libzahl
187 is known to be susceptible to timing attacks
188 (due to lack of constant time operations) and
189 data remanence attacks (due to pooling memory
190 for reuse without clearing the content of the
191 memory allocations.) Additionally, libzahl is not
192 thread-safe.
193
194 libzahl is also only designed for POSIX systems.
195 It will probably run just fine on any modern
196 system. But it makes some assumption that POSIX
197 stipulates or are unpractical to leave out from
198 machines that should support POSIX (or even
199 support modern software):
200
201 \begin{itemize}
202 \item
203 Bytes are octets.
204
205 \item
206 There is an integer type that is 64-bits wide.
207 (The compiler needs to support it, but it is not
208 strictly necessary for it to be an CPU-intrinsic,
209 but that would be favourable for performance.)
210
211 \item
212 Two's complement is used.
213 (The compiler needs to support it, but it is not
214 strictly necessary for it to be an CPU-intrinsic,
215 but that would be favourable for performance.)
216 \end{itemize}
217
218 Because of the prevalence of these properties
219 in contemporary machines, and the utilisation of
220 these properties in software, especially software
221 for POSIX and popular platforms with similar
222 properties, any new general-purpose machine must
223 have these properties, lest it be useless with
224 today's software. Therefore, libzahl can make
225 the assumption that the machine has these
226 properties. If the machine does not have these
227 properties, the compiler must compensate for
228 these machines deficiencies, making it generally
229 slower.
230
231 These limitations may be removed later. And there
232 is some code that does not make these assumptions
233 but acknowledge that it may be a case. On the other
234 hand, these limitations could be fixed, and agnostic
235 code could be rewritten to assume that these
236 restrictions are met.