1 /*
2 * mpatrol
3 * A library for controlling and tracing dynamic memory allocations.
4 * Copyright (C) 1997-2002 Graeme S. Roy <graeme.roy@analog.com>
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Library General Public
8 * License as published by the Free Software Foundation; either
9 * version 2 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Library General Public License for more details.
15 *
16 * You should have received a copy of the GNU Library General Public
17 * License along with this library; if not, write to the Free
18 * Software Foundation, Inc., 59 Temple Place, Suite 330, Boston,
19 * MA 02111-1307, USA.
20 */
21
22
23 /*
24 * Mathematical support routines. The signed and unsigned LEB128 support
25 * routines are derived from algorithms printed in the DWARF 2 debugging
26 * information format specification.
27 */
28
29
30 #include "utils.h"
31
32
33 #if MP_IDENT_SUPPORT
34 #ident "$Id: utils.c,v 1.11 2002/01/08 20:13:59 graeme Exp $"
35 #else /* MP_IDENT_SUPPORT */
36 static MP_CONST MP_VOLATILE char *utils_id = "$Id: utils.c,v 1.11 2002/01/08 20:13:59 graeme Exp $";
37 #endif /* MP_IDENT_SUPPORT */
38
39
40 #ifdef __cplusplus
41 extern "C"
42 {
43 #endif /* __cplusplus */
44
45
46 /* Return the base-two logarithm of an unsigned integer.
47 */
48
49 MP_GLOBAL
50 unsigned char
__mp_logtwo(unsigned long n)51 __mp_logtwo(unsigned long n)
52 {
53 unsigned char l;
54
55 for (l = 0; n > 0; l++, n >>= 1);
56 return (unsigned char) ((l == 0) ? 0 : l - 1);
57 }
58
59
60 /* Return the truncated square root of an unsigned integer.
61 */
62
63 MP_GLOBAL
64 unsigned long
__mp_squareroot(unsigned long n)65 __mp_squareroot(unsigned long n)
66 {
67 unsigned long r, t;
68
69 for (r = 0, t = 1; n >= t; n -= t, r++, t += 2);
70 return r;
71 }
72
73
74 #if !MP_MACROROUTINES
75 /* Determine if an unsigned integer is a power of two.
76 */
77
78 MP_GLOBAL
79 int
__mp_ispoweroftwo(unsigned long n)80 __mp_ispoweroftwo(unsigned long n)
81 {
82 return ((n > 0) && ((n & (n - 1)) == 0));
83 }
84 #endif /* MP_MACROROUTINES */
85
86
87 /* Round an unsigned integer up to the nearest power of two.
88 */
89
90 MP_GLOBAL
91 unsigned long
__mp_poweroftwo(unsigned long n)92 __mp_poweroftwo(unsigned long n)
93 {
94 if ((n == 0) || __mp_ispoweroftwo(n))
95 return n;
96 return (unsigned long) (2 << __mp_logtwo(n));
97 }
98
99
100 #if !MP_MACROROUTINES
101 /* Round an unsigned integer down to a specified power of two alignment.
102 */
103
104 MP_GLOBAL
105 unsigned long
__mp_rounddown(unsigned long n,unsigned long a)106 __mp_rounddown(unsigned long n, unsigned long a)
107 {
108 return n & ~(a - 1);
109 }
110 #endif /* MP_MACROROUTINES */
111
112
113 #if !MP_MACROROUTINES
114 /* Round an unsigned integer up to a specified power of two alignment.
115 */
116
117 MP_GLOBAL
118 unsigned long
__mp_roundup(unsigned long n,unsigned long a)119 __mp_roundup(unsigned long n, unsigned long a)
120 {
121 return ((n - 1) & ~(a - 1)) + a;
122 }
123 #endif /* MP_MACROROUTINES */
124
125
126 /* Convert a signed integer to a signed LEB128 number.
127 */
128
129 MP_GLOBAL
130 void *
__mp_encodesleb128(long n,size_t * l)131 __mp_encodesleb128(long n, size_t *l)
132 {
133 static unsigned char b[32];
134 size_t i;
135 int p, s;
136
137 i = 0;
138 p = (n >= 0);
139 do
140 {
141 b[i] = n & 0x7F;
142 n >>= 7;
143 if (!p)
144 n |= -(1UL << ((sizeof(long) << 3) - 7));
145 s = b[i] & 0x40;
146 if (((n != 0) || (s != 0)) && ((n != -1) || (s == 0)))
147 b[i] |= 0x80;
148 }
149 while (b[i++] & 0x80);
150 *l = i;
151 return b;
152 }
153
154
155 /* Convert an unsigned integer to an unsigned LEB128 number.
156 */
157
158 MP_GLOBAL
159 void *
__mp_encodeuleb128(unsigned long n,size_t * l)160 __mp_encodeuleb128(unsigned long n, size_t *l)
161 {
162 static unsigned char b[32];
163 size_t i;
164
165 i = 0;
166 do
167 {
168 b[i] = n & 0x7F;
169 if (n >>= 7)
170 b[i] |= 0x80;
171 }
172 while (b[i++] & 0x80);
173 *l = i;
174 return b;
175 }
176
177
178 /* Convert a signed LEB128 number to a signed integer.
179 */
180
181 MP_GLOBAL
182 long
__mp_decodesleb128(void * d,size_t * l)183 __mp_decodesleb128(void *d, size_t *l)
184 {
185 unsigned char *b;
186 long n;
187 unsigned char s;
188
189 b = (unsigned char *) d;
190 n = 0;
191 s = 0;
192 do
193 {
194 n |= (*b & 0x7F) << s;
195 s += 7;
196 }
197 while (*b++ & 0x80);
198 if ((s < sizeof(long) << 3) && (*(b - 1) & 0x40))
199 n |= -(1 << s);
200 *l = (size_t) (b - (unsigned char *) d);
201 return n;
202 }
203
204
205 /* Convert an unsigned LEB128 number to an unsigned integer.
206 */
207
208 MP_GLOBAL
209 unsigned long
__mp_decodeuleb128(void * d,size_t * l)210 __mp_decodeuleb128(void *d, size_t *l)
211 {
212 unsigned char *b;
213 unsigned long n;
214 unsigned char s;
215
216 b = (unsigned char *) d;
217 n = 0;
218 s = 0;
219 do
220 {
221 n |= (*b & 0x7F) << s;
222 s += 7;
223 }
224 while (*b++ & 0x80);
225 *l = (size_t) (b - (unsigned char *) d);
226 return n;
227 }
228
229
230 #ifdef __cplusplus
231 }
232 #endif /* __cplusplus */
233