1 /* AirScan (a.k.a. eSCL) backend for SANE
2 *
3 * Copyright (C) 2019 and up by Alexander Pevzner (pzz@apevzner.com)
4 * See LICENSE for license terms and conditions
5 *
6 * Miscellaneous mathematical functions
7 */
8
9 #include "airscan.h"
10
11 #pragma GCC diagnostic ignored "-Wunused-result"
12
13 /* Find greatest common divisor of two positive integers
14 */
15 SANE_Word
math_gcd(SANE_Word x,SANE_Word y)16 math_gcd (SANE_Word x, SANE_Word y)
17 {
18 log_assert(NULL, x > 0 && y > 0);
19
20 while (x != y) {
21 if (x > y) {
22 x -= y;
23 } else {
24 y -= x;
25 }
26 }
27
28 return x;
29 }
30
31 /* Find least common multiple of two positive integers
32 */
33 SANE_Word
math_lcm(SANE_Word x,SANE_Word y)34 math_lcm (SANE_Word x, SANE_Word y)
35 {
36 return (x * y) / math_gcd(x, y);
37 }
38
39 /* Check two ranges for equivalency
40 */
41 static inline bool
math_range_eq(const SANE_Range * r1,const SANE_Range * r2)42 math_range_eq (const SANE_Range *r1, const SANE_Range *r2)
43 {
44 return r1->min == r2->min && r1->max == r2->max && r1->quant == r2->quant;
45 }
46
47 /* Check two ranges for overlapping
48 */
49 static inline bool
math_range_ovp(const SANE_Range * r1,const SANE_Range * r2)50 math_range_ovp (const SANE_Range *r1, const SANE_Range *r2)
51 {
52 return r1->max >= r2->min && r2->max >= r1->min;
53 }
54
55 /* Merge two ranges, if possible
56 */
57 bool
math_range_merge(SANE_Range * out,const SANE_Range * r1,const SANE_Range * r2)58 math_range_merge (SANE_Range *out, const SANE_Range *r1, const SANE_Range *r2)
59 {
60 /* Check for trivial cases */
61 if (math_range_eq(r1, r2)) {
62 *out = *r1;
63 return true;
64 }
65
66 if (!math_range_ovp(r1, r2)) {
67 return false;
68 }
69
70 /* Ranges have equal quantization? If yes, just adjust min and max */
71 if (r1->quant == r2->quant) {
72 out->min = math_max(r1->min, r2->min);
73 out->max = math_min(r1->max, r2->max);
74 out->quant = r1->quant;
75 return true;
76 }
77
78 /* At least one of ranges don't have quantization? */
79 if (!r1->quant || !r2->quant) {
80 /* To avoid code duplication, normalize things, so
81 * r1 does have quantization and r2 doesn't. Note,
82 * situation when both ranges don't have quantization
83 * was covered before, when we checked for equal quantization
84 */
85 if (r1->quant == 0) {
86 const SANE_Range *tmp = r1;
87 r1 = r2;
88 r2 = tmp;
89 }
90
91 /* And fit r2 within r1 */
92 out->min = math_range_fit(r1, r2->min);
93 out->max = math_range_fit(r1, r2->max);
94 out->quant = r1->quant;
95 return true;
96 }
97
98 /* Now the most difficult case */
99 SANE_Word quant = math_lcm(r1->quant, r2->quant);
100 SANE_Word min, max, bounds_min, bounds_max;
101
102 bounds_min = math_max(r1->min, r2->min);
103 bounds_max = math_min(r1->max, r2->max);
104
105 for (min = math_min(r1->min, r2->min); min < bounds_min; min += quant)
106 ;
107
108 if (min > bounds_max) {
109 return false;
110 }
111
112 for (max = min; max + quant <= bounds_max; max += quant)
113 ;
114
115 out->min = min;
116 out->max = max;
117 out->quant = quant;
118
119 return true;
120 }
121
122 /* Choose nearest integer in range
123 */
124 SANE_Word
math_range_fit(const SANE_Range * r,SANE_Word i)125 math_range_fit(const SANE_Range *r, SANE_Word i)
126 {
127 if (i < r->min) {
128 return r->min;
129 }
130
131 if (i > r->max) {
132 return r->max;
133 }
134
135 if (r->quant == 0) {
136 return i;
137 }
138
139 i -= r->min;
140 i = ((i + r->quant / 2) / r->quant) * r->quant;
141 i += r->min;
142
143 return math_min(i, r->max);
144 }
145
146 /* Format millimeters, for printing
147 */
148 char*
math_fmt_mm(SANE_Word mm,char buf[])149 math_fmt_mm (SANE_Word mm, char buf[])
150 {
151 double mmd = SANE_UNFIX(mm);
152 double integer, fraction;
153
154 integer = floor(mmd);
155 fraction = mmd - integer;
156
157 if (fraction != 0) {
158 sprintf(buf, "%d.%2.2d", (int) integer, (int) round(fraction * 100));
159 } else {
160 sprintf(buf, "%d", (int) integer);
161 }
162
163 return buf;
164 }
165
166 /* Genrate random 32-bit integer
167 */
168 uint32_t
math_rand_u32(void)169 math_rand_u32 (void)
170 {
171 uint32_t r;
172 rand_bytes(&r, sizeof(r));
173 return r;
174 }
175
176 /* Generate random integer in range [0...max], inclusively
177 */
178 uint32_t
math_rand_max(uint32_t max)179 math_rand_max (uint32_t max)
180 {
181 uint32_t mask, tmp;
182
183 for (mask = 0, tmp = max; tmp != 0; tmp >>= 1) {
184 mask |= tmp;
185 }
186
187 do {
188 tmp = math_rand_u32() & mask;
189 } while (tmp > max);
190
191 return tmp;
192 }
193
194 /* Generate random integer in range [min...max], inclusively
195 */
196 uint32_t
math_rand_range(uint32_t min,uint32_t max)197 math_rand_range (uint32_t min, uint32_t max)
198 {
199 /* Normalize range */
200 if (min == max) {
201 return min;
202 }
203
204 if (min > max) {
205 uint32_t tmp = max;
206 max = min;
207 min = tmp;
208 }
209
210 /* Generate random number */
211 return min + math_rand_max(max - min);
212 }
213
214 /* vim:ts=8:sw=4:et
215 */
216