1 // stb_divide.h - v0.92 - public domain - Sean Barrett, Feb 2010
2 // Three kinds of divide/modulus of signed integers.
3 //
4 // HISTORY
5 //
6 // v0.92 2019-02-25 Fix warning
7 // v0.91 2010-02-27 Fix euclidean division by INT_MIN for non-truncating C
8 // Check result with 64-bit math to catch such cases
9 // v0.90 2010-02-24 First public release
10 //
11 // USAGE
12 //
13 // In *ONE* source file, put:
14 //
15 // #define STB_DIVIDE_IMPLEMENTATION
16 // // #define C_INTEGER_DIVISION_TRUNCATES // see Note 1
17 // // #define C_INTEGER_DIVISION_FLOORS // see Note 2
18 // #include "stb_divide.h"
19 //
20 // Other source files should just include stb_divide.h
21 //
22 // Note 1: On platforms/compilers that you know signed C division
23 // truncates, you can #define C_INTEGER_DIVISION_TRUNCATES.
24 //
25 // Note 2: On platforms/compilers that you know signed C division
26 // floors (rounds to negative infinity), you can #define
27 // C_INTEGER_DIVISION_FLOORS.
28 //
29 // You can #define STB_DIVIDE_TEST in which case the implementation
30 // will generate a main() and compiling the result will create a
31 // program that tests the implementation. Run it with no arguments
32 // and any output indicates an error; run it with any argument and
33 // it will also print the test results. Define STB_DIVIDE_TEST_64
34 // to a 64-bit integer type to avoid overflows in the result-checking
35 // which give false negatives.
36 //
37 // ABOUT
38 //
39 // This file provides three different consistent divide/mod pairs
40 // implemented on top of arbitrary C/C++ division, including correct
41 // handling of overflow of intermediate calculations:
42 //
43 // trunc: a/b truncates to 0, a%b has same sign as a
44 // floor: a/b truncates to -inf, a%b has same sign as b
45 // eucl: a/b truncates to sign(b)*inf, a%b is non-negative
46 //
47 // Not necessarily optimal; I tried to keep it generally efficient,
48 // but there may be better ways.
49 //
50 // Briefly, for those who are not familiar with the problem, we note
51 // the reason these divides exist and are interesting:
52 //
53 // 'trunc' is easy to implement in hardware (strip the signs,
54 // compute, reapply the signs), thus is commonly defined
55 // by many languages (including C99)
56 //
57 // 'floor' is simple to define and better behaved than trunc;
58 // for example it divides integers into fixed-size buckets
59 // without an extra-wide bucket at 0, and for a fixed
60 // divisor N there are only |N| possible moduli.
61 //
62 // 'eucl' guarantees fixed-sized buckets *and* a non-negative
63 // modulus and defines division to be whatever is needed
64 // to achieve that result.
65 //
66 // See "The Euclidean definition of the functions div and mod"
67 // by Raymond Boute (1992), or "Division and Modulus for Computer
68 // Scientists" by Daan Leijen (2001)
69 //
70 // We assume of the built-in C division:
71 // (a) modulus is the remainder for the corresponding division
72 // (b) a/b truncates if a and b are the same sign
73 //
74 // Property (a) requires (a/b)*b + (a%b)==a, and is required by C.
75 // Property (b) seems to be true of all hardware but is *not* satisfied
76 // by the euclidean division operator we define, so it's possibly not
77 // always true. If any such platform turns up, we can add more cases.
78 // (Possibly only stb_div_trunc currently relies on property (b).)
79 //
80 // LICENSE
81 //
82 // See end of file for license information.
83
84
85 #ifndef INCLUDE_STB_DIVIDE_H
86 #define INCLUDE_STB_DIVIDE_H
87
88 #ifdef __cplusplus
89 extern "C" {
90 #endif
91
92 extern int stb_div_trunc(int value_to_be_divided, int value_to_divide_by);
93 extern int stb_div_floor(int value_to_be_divided, int value_to_divide_by);
94 extern int stb_div_eucl (int value_to_be_divided, int value_to_divide_by);
95 extern int stb_mod_trunc(int value_to_be_divided, int value_to_divide_by);
96 extern int stb_mod_floor(int value_to_be_divided, int value_to_divide_by);
97 extern int stb_mod_eucl (int value_to_be_divided, int value_to_divide_by);
98
99 #ifdef __cplusplus
100 }
101 #endif
102
103 #ifdef STB_DIVIDE_IMPLEMENTATION
104
105 #if defined(__STDC_VERSION) && __STDC_VERSION__ >= 19901
106 #ifndef C_INTEGER_DIVISION_TRUNCATES
107 #define C_INTEGER_DIVISION_TRUNCATES
108 #endif
109 #endif
110
111 #ifndef INT_MIN
112 #include <limits.h> // if you have no limits.h, #define INT_MIN yourself
113 #endif
114
115 // the following macros are designed to allow testing
116 // other platforms by simulating them
117 #ifndef STB_DIVIDE_TEST_FLOOR
118 #define stb__div(a,b) ((a)/(b))
119 #define stb__mod(a,b) ((a)%(b))
120 #else
121 // implement floor-style divide on trunc platform
122 #ifndef C_INTEGER_DIVISION_TRUNCATES
123 #error "floor test requires truncating division"
124 #endif
125 #undef C_INTEGER_DIVISION_TRUNCATES
stb__div(int v1,int v2)126 int stb__div(int v1, int v2)
127 {
128 int q = v1/v2, r = v1%v2;
129 if ((r > 0 && v2 < 0) || (r < 0 && v2 > 0))
130 return q-1;
131 else
132 return q;
133 }
134
stb__mod(int v1,int v2)135 int stb__mod(int v1, int v2)
136 {
137 int r = v1%v2;
138 if ((r > 0 && v2 < 0) || (r < 0 && v2 > 0))
139 return r+v2;
140 else
141 return r;
142 }
143 #endif
144
stb_div_trunc(int v1,int v2)145 int stb_div_trunc(int v1, int v2)
146 {
147 #ifdef C_INTEGER_DIVISION_TRUNCATES
148 return v1/v2;
149 #else
150 if (v1 >= 0 && v2 <= 0)
151 return -stb__div(-v1,v2); // both negative to avoid overflow
152 if (v1 <= 0 && v2 >= 0)
153 if (v1 != INT_MIN)
154 return -stb__div(v1,-v2); // both negative to avoid overflow
155 else
156 return -stb__div(v1+v2,-v2)-1; // push v1 away from wrap point
157 else
158 return v1/v2; // same sign, so expect truncation
159 #endif
160 }
161
stb_div_floor(int v1,int v2)162 int stb_div_floor(int v1, int v2)
163 {
164 #ifdef C_INTEGER_DIVISION_FLOORS
165 return v1/v2;
166 #else
167 if (v1 >= 0 && v2 < 0) {
168 if ((-v1)+v2+1 < 0) // check if increasing v1's magnitude overflows
169 return -stb__div(-v1+v2+1,v2); // nope, so just compute it
170 else
171 return -stb__div(-v1,v2) + ((-v1)%v2 ? -1 : 0);
172 }
173 if (v1 < 0 && v2 >= 0) {
174 if (v1 != INT_MIN) {
175 if (v1-v2+1 < 0) // check if increasing v1's magnitude overflows
176 return -stb__div(v1-v2+1,-v2); // nope, so just compute it
177 else
178 return -stb__div(-v1,v2) + (stb__mod(v1,-v2) ? -1 : 0);
179 } else // it must be possible to compute -(v1+v2) without overflowing
180 return -stb__div(-(v1+v2),v2) + (stb__mod(-(v1+v2),v2) ? -2 : -1);
181 } else
182 return v1/v2; // same sign, so expect truncation
183 #endif
184 }
185
stb_div_eucl(int v1,int v2)186 int stb_div_eucl(int v1, int v2)
187 {
188 int q,r;
189 #ifdef C_INTEGER_DIVISION_TRUNCATES
190 q = v1/v2;
191 r = v1%v2;
192 #else
193 // handle every quadrant separately, since we can't rely on q and r flor
194 if (v1 >= 0)
195 if (v2 >= 0)
196 return stb__div(v1,v2);
197 else if (v2 != INT_MIN)
198 q = -stb__div(v1,-v2), r = stb__mod(v1,-v2);
199 else
200 q = 0, r = v1;
201 else if (v1 != INT_MIN)
202 if (v2 >= 0)
203 q = -stb__div(-v1,v2), r = -stb__mod(-v1,v2);
204 else if (v2 != INT_MIN)
205 q = stb__div(-v1,-v2), r = -stb__mod(-v1,-v2);
206 else // if v2 is INT_MIN, then we can't use -v2, but we can't divide by v2
207 q = 1, r = v1-q*v2;
208 else // if v1 is INT_MIN, we have to move away from overflow place
209 if (v2 >= 0)
210 q = -stb__div(-(v1+v2),v2)-1, r = -stb__mod(-(v1+v2),v2);
211 else
212 q = stb__div(-(v1-v2),-v2)+1, r = -stb__mod(-(v1-v2),-v2);
213 #endif
214 if (r >= 0)
215 return q;
216 else
217 return q + (v2 > 0 ? -1 : 1);
218 }
219
stb_mod_trunc(int v1,int v2)220 int stb_mod_trunc(int v1, int v2)
221 {
222 #ifdef C_INTEGER_DIVISION_TRUNCATES
223 return v1%v2;
224 #else
225 if (v1 >= 0) { // modulus result should always be positive
226 int r = stb__mod(v1,v2);
227 if (r >= 0)
228 return r;
229 else
230 return r + (v2 > 0 ? v2 : -v2);
231 } else { // modulus result should always be negative
232 int r = stb__mod(v1,v2);
233 if (r <= 0)
234 return r;
235 else
236 return r - (v2 > 0 ? v2 : -v2);
237 }
238 #endif
239 }
240
stb_mod_floor(int v1,int v2)241 int stb_mod_floor(int v1, int v2)
242 {
243 #ifdef C_INTEGER_DIVISION_FLOORS
244 return v1%v2;
245 #else
246 if (v2 >= 0) { // result should always be positive
247 int r = stb__mod(v1,v2);
248 if (r >= 0)
249 return r;
250 else
251 return r + v2;
252 } else { // result should always be negative
253 int r = stb__mod(v1,v2);
254 if (r <= 0)
255 return r;
256 else
257 return r + v2;
258 }
259 #endif
260 }
261
stb_mod_eucl(int v1,int v2)262 int stb_mod_eucl(int v1, int v2)
263 {
264 int r = stb__mod(v1,v2);
265
266 if (r >= 0)
267 return r;
268 else
269 return r + (v2 > 0 ? v2 : -v2); // abs()
270 }
271
272 #ifdef STB_DIVIDE_TEST
273 #include <stdio.h>
274 #include <math.h>
275 #include <limits.h>
276
277 int show=0;
278
stbdiv_check(int q,int r,int a,int b,char * type,int dir)279 void stbdiv_check(int q, int r, int a, int b, char *type, int dir)
280 {
281 if ((dir > 0 && r < 0) || (dir < 0 && r > 0))
282 fprintf(stderr, "FAILED: %s(%d,%d) remainder %d in wrong direction\n", type,a,b,r);
283 else
284 if (b != INT_MIN) // can't compute abs(), but if b==INT_MIN all remainders are valid
285 if (r <= -abs(b) || r >= abs(b))
286 fprintf(stderr, "FAILED: %s(%d,%d) remainder %d out of range\n", type,a,b,r);
287 #ifdef STB_DIVIDE_TEST_64
288 {
289 STB_DIVIDE_TEST_64 q64 = q, r64=r, a64=a, b64=b;
290 if (q64*b64+r64 != a64)
291 fprintf(stderr, "FAILED: %s(%d,%d) remainder %d doesn't match quotient %d\n", type,a,b,r,q);
292 }
293 #else
294 if (q*b+r != a)
295 fprintf(stderr, "FAILED: %s(%d,%d) remainder %d doesn't match quotient %d\n", type,a,b,r,q);
296 #endif
297 }
298
test(int a,int b)299 void test(int a, int b)
300 {
301 int q,r;
302 if (show) printf("(%+11d,%+d) | ", a,b);
303 q = stb_div_trunc(a,b), r = stb_mod_trunc(a,b);
304 if (show) printf("(%+11d,%+2d) ", q,r); stbdiv_check(q,r,a,b, "trunc",a);
305 q = stb_div_floor(a,b), r = stb_mod_floor(a,b);
306 if (show) printf("(%+11d,%+2d) ", q,r); stbdiv_check(q,r,a,b, "floor",b);
307 q = stb_div_eucl (a,b), r = stb_mod_eucl (a,b);
308 if (show) printf("(%+11d,%+2d)\n", q,r); stbdiv_check(q,r,a,b, "euclidean",1);
309 }
310
testh(int a,int b)311 void testh(int a, int b)
312 {
313 int q,r;
314 if (show) printf("(%08x,%08x) |\n", a,b);
315 q = stb_div_trunc(a,b), r = stb_mod_trunc(a,b); stbdiv_check(q,r,a,b, "trunc",a);
316 if (show) printf(" (%08x,%08x)", q,r);
317 q = stb_div_floor(a,b), r = stb_mod_floor(a,b); stbdiv_check(q,r,a,b, "floor",b);
318 if (show) printf(" (%08x,%08x)", q,r);
319 q = stb_div_eucl (a,b), r = stb_mod_eucl (a,b); stbdiv_check(q,r,a,b, "euclidean",1);
320 if (show) printf(" (%08x,%08x)\n ", q,r);
321 }
322
main(int argc,char ** argv)323 int main(int argc, char **argv)
324 {
325 if (argc > 1) show=1;
326
327 test(8,3);
328 test(8,-3);
329 test(-8,3);
330 test(-8,-3);
331 test(1,2);
332 test(1,-2);
333 test(-1,2);
334 test(-1,-2);
335 test(8,4);
336 test(8,-4);
337 test(-8,4);
338 test(-8,-4);
339
340 test(INT_MAX,1);
341 test(INT_MIN,1);
342 test(INT_MIN+1,1);
343 test(INT_MAX,-1);
344 //test(INT_MIN,-1); // this traps in MSVC, so we leave it untested
345 test(INT_MIN+1,-1);
346 test(INT_MIN,-2);
347 test(INT_MIN+1,2);
348 test(INT_MIN+1,-2);
349 test(INT_MAX,2);
350 test(INT_MAX,-2);
351 test(INT_MIN+1,2);
352 test(INT_MIN+1,-2);
353 test(INT_MIN,2);
354 test(INT_MIN,-2);
355 test(INT_MIN,7);
356 test(INT_MIN,-7);
357 test(INT_MIN+1,4);
358 test(INT_MIN+1,-4);
359
360 testh(-7, INT_MIN);
361 testh(-1, INT_MIN);
362 testh(1, INT_MIN);
363 testh(7, INT_MIN);
364
365 testh(INT_MAX-1, INT_MIN);
366 testh(INT_MAX, INT_MIN);
367 testh(INT_MIN, INT_MIN);
368 testh(INT_MIN+1, INT_MIN);
369
370 testh(INT_MAX-1, INT_MAX);
371 testh(INT_MAX , INT_MAX);
372 testh(INT_MIN , INT_MAX);
373 testh(INT_MIN+1, INT_MAX);
374
375 return 0;
376 }
377 #endif // STB_DIVIDE_TEST
378 #endif // STB_DIVIDE_IMPLEMENTATION
379 #endif // INCLUDE_STB_DIVIDE_H
380
381 /*
382 ------------------------------------------------------------------------------
383 This software is available under 2 licenses -- choose whichever you prefer.
384 ------------------------------------------------------------------------------
385 ALTERNATIVE A - MIT License
386 Copyright (c) 2017 Sean Barrett
387 Permission is hereby granted, free of charge, to any person obtaining a copy of
388 this software and associated documentation files (the "Software"), to deal in
389 the Software without restriction, including without limitation the rights to
390 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
391 of the Software, and to permit persons to whom the Software is furnished to do
392 so, subject to the following conditions:
393 The above copyright notice and this permission notice shall be included in all
394 copies or substantial portions of the Software.
395 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
396 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
397 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
398 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
399 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
400 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
401 SOFTWARE.
402 ------------------------------------------------------------------------------
403 ALTERNATIVE B - Public Domain (www.unlicense.org)
404 This is free and unencumbered software released into the public domain.
405 Anyone is free to copy, modify, publish, use, compile, sell, or distribute this
406 software, either in source code form or as a compiled binary, for any purpose,
407 commercial or non-commercial, and by any means.
408 In jurisdictions that recognize copyright laws, the author or authors of this
409 software dedicate any and all copyright interest in the software to the public
410 domain. We make this dedication for the benefit of the public at large and to
411 the detriment of our heirs and successors. We intend this dedication to be an
412 overt act of relinquishment in perpetuity of all present and future rights to
413 this software under copyright law.
414 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
415 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
416 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
417 AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
418 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
419 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
420 ------------------------------------------------------------------------------
421 */
422