chiark / gitweb /
examples/disorder.init.in: Read settings from `/etc/default/disorder'.
[disorder] / lib / basen.c
1 /*
2  * This file is part of DisOrder.
3  * Copyright (C) 2005, 2007, 2008 Richard Kettlewell
4  *
5  * This program is free software: you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License as published by
7  * the Free Software Foundation, either version 3 of the License, or
8  * (at your option) any later version.
9  * 
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  * 
15  * You should have received a copy of the GNU General Public License
16  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
17  */
18 /** @file lib/basen.c @brief Arbitrary base conversion 
19  *
20  * The functions in this file handle arbitrary-size non-negative integers,
21  * represented as a bigendian (MSW first) sequence of @c unsigned @c long
22  * words.  The words themselves use the native byte order.
23  */
24
25 #include "common.h"
26
27 #include "basen.h"
28
29 /** @brief Test whether v is 0
30  * @param v Pointer to bigendian bignum
31  * @param nwords Length of bignum
32  * @return !v
33  */
34 static int zero(const uint32_t *v, int nwords) {
35   int n;
36
37   for(n = 0; n < nwords && !v[n]; ++n)
38     ;
39   return n == nwords;
40 }
41
42 /** @brief Divide v by m returning the remainder.
43  * @param v Pointer to bigendian bignum
44  * @param nwords Length of bignum
45  * @param m Divisor (must not be 0)
46  * @return Remainder
47  *
48  * The quotient is stored in @p v.
49  */
50 static unsigned divide(uint32_t *v, int nwords, unsigned long m) {
51   unsigned long r = 0, a, b;
52   int n;
53
54   /* we do the divide 16 bits at a time */
55   for(n = 0; n < nwords; ++n) {
56     a = v[n] >> 16;
57     b = v[n] & 0xFFFF;
58     a += r << 16;
59     r = a % m;
60     a /= m;
61     b += r << 16;
62     r = b % m;
63     b /= m;
64     v[n] = (a << 16) + b;
65   }
66   return r;
67 }
68
69 /** @brief Multiple v by m and add a
70  * @param v Pointer to bigendian bignum
71  * @param nwords Length of bignum
72  * @param m Value to multiply by
73  * @param a Value to add
74  * @return 0 on success, non-0 on overflow
75  *
76  * Does v = m * v + a.
77  */
78 static int mla(uint32_t *v, int nwords, uint32_t m, uint32_t a) {
79   int n = nwords - 1;
80   uint32_t carry = a;
81
82   while(n >= 0) {
83     const uint64_t p = (uint64_t)v[n] * m + carry;
84     carry = (uint32_t)(p >> 32);
85     v[n] = (uint32_t)p;
86     --n;
87   }
88   /* If there is still a carry then we overflowed */
89   return !!carry;
90 }
91
92 static const char basen_chars[] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
93
94 /** @brief Convert v to a chosen base
95  * @param v Pointer to bigendian bignum (modified!)
96  * @param nwords Length of bignum
97  * @param buffer Output buffer
98  * @param bufsize Size of output buffer
99  * @param base Number base (2..62)
100  * @return 0 on success, -1 if the buffer is too small
101  *
102  * Converts @p v to a string in the given base using decimal digits, lower case
103  * letters and upper case letters as digits.
104  *
105  * The inverse of nesab().
106  */
107 int basen(uint32_t *v,
108           int nwords,
109           char buffer[],
110           size_t bufsize,
111           unsigned base) {
112   size_t i = bufsize;
113   
114   do {
115     if(i <= 1)
116       return -1;                        /* overflow */
117     buffer[--i] = basen_chars[divide(v, nwords, base)];
118   } while(!zero(v, nwords));
119   memmove(buffer, buffer + i, bufsize - i);
120   buffer[bufsize - i] = 0;
121   return 0;
122 }
123
124 /** @brief Convert a string back to a large integer in an arbitrary base
125  * @param v Where to store result as a bigendian bignum
126  * @param nwords Space available in @p v
127  * @param s Input string
128  * @param base Number base (2..62)
129  * @return 0 on success, non-0 on overflow or invalid input
130  *
131  * The inverse of basen().  If the number is much smaller than the buffer then
132  * the first words will be 0.
133  */
134 int nesab(uint32_t *v,
135           int nwords,
136           const char *s,
137           unsigned base) {
138   /* Initialize to 0 */
139   memset(v, 0, nwords * sizeof *v);
140   while(*s) {
141     const char *dp = strchr(basen_chars, *s++);
142     if(!dp)
143       return -1;
144     if(mla(v, nwords, base, dp - basen_chars))
145       return -1;
146   }
147   return 0;
148 }
149
150 /*
151 Local Variables:
152 c-basic-offset:2
153 comment-column:40
154 fill-column:79
155 End:
156 */