Line data Source code
1 : /*
2 : * liblierre - decoder.c
3 : *
4 : * This file is part of liblierre.
5 : *
6 : * Author: Go Kudo <zeriyoshi@gmail.com>
7 : * SPDX-License-Identifier: MIT AND ISC
8 : *
9 : * This file contains code derived from quirc (https://github.com/dlbeer/quirc).
10 : * Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com>
11 : * Licensed under the ISC License.
12 : */
13 :
14 : #include "../internal/decoder.h"
15 :
16 : #if LIERRE_USE_SIMD
17 : #include "../internal/simd.h"
18 : #endif
19 :
20 : #define LIERRE_HISTOGRAM_SIZE 256
21 :
22 121 : static inline uint8_t compute_otsu_threshold(const decoder_t *decoder)
23 : {
24 : const uint8_t *image_ptr;
25 : uint64_t total_sum_int;
26 121 : uint32_t histogram[LIERRE_HISTOGRAM_SIZE] = {0}, total_pixels, foreground_count, background_count,
27 : optimal_threshold, i;
28 : uint8_t pixel_value;
29 : size_t remaining;
30 : double total_sum, foreground_sum, foreground_mean, background_mean, between_class_variance, max_variance;
31 :
32 121 : total_pixels = (uint32_t)(decoder->w * decoder->h);
33 :
34 121 : image_ptr = decoder->image;
35 121 : remaining = (size_t)total_pixels;
36 121 : total_sum_int = 0;
37 123405702 : while (remaining--) {
38 123405581 : pixel_value = *image_ptr++;
39 123405581 : histogram[pixel_value]++;
40 123405581 : total_sum_int += pixel_value;
41 : }
42 121 : total_sum = (double)total_sum_int;
43 :
44 121 : foreground_sum = 0.0;
45 121 : foreground_count = 0;
46 121 : max_variance = 0.0;
47 121 : optimal_threshold = 0;
48 :
49 29921 : for (i = 0; i < LIERRE_HISTOGRAM_SIZE; i++) {
50 29921 : foreground_count += histogram[i];
51 29921 : if (foreground_count == 0) {
52 1583 : continue;
53 : }
54 :
55 28338 : background_count = total_pixels - foreground_count;
56 28338 : if (background_count == 0) {
57 121 : break;
58 : }
59 :
60 28217 : foreground_sum += (double)i * histogram[i];
61 28217 : foreground_mean = foreground_sum / foreground_count;
62 28217 : background_mean = (total_sum - foreground_sum) / background_count;
63 28217 : between_class_variance = (foreground_mean - background_mean) * (foreground_mean - background_mean) *
64 28217 : foreground_count * background_count;
65 :
66 28217 : if (between_class_variance >= max_variance) {
67 26895 : optimal_threshold = i;
68 26895 : max_variance = between_class_variance;
69 : }
70 : }
71 :
72 121 : return (uint8_t)optimal_threshold;
73 : }
74 :
75 121 : static inline void binarize_image(decoder_t *decoder, uint8_t threshold)
76 : {
77 : int32_t x, y;
78 : uint8_t *row, pixel_value;
79 : size_t total;
80 :
81 121 : total = (size_t)decoder->w * (size_t)decoder->h;
82 :
83 : #if LIERRE_USE_SIMD && defined(LIERRE_SIMD_AVX2)
84 : {
85 : __m256i thresh_vec, data;
86 : __m256i black_lo, white_lo, result_lo;
87 : __m128i data128;
88 : size_t i, simd_count;
89 :
90 121 : simd_count = total & ~15ULL;
91 :
92 7712950 : for (i = 0; i < simd_count; i += 16) {
93 15425658 : data128 = _mm_loadu_si128((const __m128i *)(decoder->image + i));
94 7712829 : data = _mm256_cvtepu8_epi16(data128);
95 :
96 15425658 : thresh_vec = _mm256_set1_epi16((int16_t)threshold);
97 7712829 : black_lo = _mm256_set1_epi16((int16_t)LIERRE_PIXEL_BLACK);
98 7712829 : white_lo = _mm256_set1_epi16((int16_t)LIERRE_PIXEL_WHITE);
99 :
100 7712829 : result_lo = _mm256_blendv_epi8(white_lo, black_lo, _mm256_cmpgt_epi16(thresh_vec, data));
101 :
102 7712829 : _mm256_storeu_si256((__m256i *)(decoder->pixels + i), result_lo);
103 : }
104 :
105 438 : for (i = simd_count; i < total; i++) {
106 317 : decoder->pixels[i] = (decoder->image[i] < threshold) ? LIERRE_PIXEL_BLACK : LIERRE_PIXEL_WHITE;
107 : }
108 : }
109 : #elif LIERRE_USE_SIMD && defined(LIERRE_SIMD_NEON)
110 : {
111 : uint8x8_t data8, thresh_vec8;
112 : uint16x8_t data16, mask16, black_vec, white_vec, result;
113 : size_t i, simd_count;
114 :
115 : black_vec = vdupq_n_u16(LIERRE_PIXEL_BLACK);
116 : white_vec = vdupq_n_u16(LIERRE_PIXEL_WHITE);
117 :
118 : simd_count = total & ~7ULL;
119 :
120 : for (i = 0; i < simd_count; i += 8) {
121 : data8 = vld1_u8(decoder->image + i);
122 : data16 = vmovl_u8(data8);
123 : mask16 = vcltq_u16(data16, vdupq_n_u16(threshold));
124 : result = vbslq_u16(mask16, black_vec, white_vec);
125 : vst1q_u16(decoder->pixels + i, result);
126 : }
127 :
128 : for (i = simd_count; i < total; i++) {
129 : decoder->pixels[i] = (decoder->image[i] < threshold) ? LIERRE_PIXEL_BLACK : LIERRE_PIXEL_WHITE;
130 : }
131 : }
132 : #elif LIERRE_USE_SIMD && defined(LIERRE_SIMD_WASM)
133 : {
134 : v128_t data8, data16_lo, data16_hi, thresh_vec, black_vec, white_vec, mask_lo, mask_hi, result_lo, result_hi;
135 : size_t i, simd_count;
136 :
137 : thresh_vec = wasm_u16x8_splat(threshold);
138 : black_vec = wasm_u16x8_splat(LIERRE_PIXEL_BLACK);
139 : white_vec = wasm_u16x8_splat(LIERRE_PIXEL_WHITE);
140 :
141 : simd_count = total & ~15ULL;
142 :
143 : for (i = 0; i < simd_count; i += 16) {
144 : data8 = wasm_v128_load(decoder->image + i);
145 : data16_lo = wasm_u16x8_extend_low_u8x16(data8);
146 : data16_hi = wasm_u16x8_extend_high_u8x16(data8);
147 :
148 : mask_lo = wasm_u16x8_lt(data16_lo, thresh_vec);
149 : mask_hi = wasm_u16x8_lt(data16_hi, thresh_vec);
150 :
151 : result_lo = wasm_v128_bitselect(black_vec, white_vec, mask_lo);
152 : result_hi = wasm_v128_bitselect(black_vec, white_vec, mask_hi);
153 :
154 : wasm_v128_store(decoder->pixels + i, result_lo);
155 : wasm_v128_store(decoder->pixels + i + 8, result_hi);
156 : }
157 :
158 : for (i = simd_count; i < total; i++) {
159 : decoder->pixels[i] = (decoder->image[i] < threshold) ? LIERRE_PIXEL_BLACK : LIERRE_PIXEL_WHITE;
160 : }
161 : }
162 : #else
163 : for (y = 0; y < decoder->h; y++) {
164 : row = decoder->image + y * decoder->w;
165 : for (x = 0; x < decoder->w; x++) {
166 : pixel_value = row[x];
167 : decoder->pixels[y * decoder->w + x] = (pixel_value < threshold) ? LIERRE_PIXEL_BLACK : LIERRE_PIXEL_WHITE;
168 : }
169 : }
170 :
171 : (void)total;
172 : #endif
173 121 : }
174 :
175 121 : static inline int32_t decoder_resize(decoder_t *decoder, int32_t width, int32_t height)
176 : {
177 : lierre_pixel_t *pixels;
178 : flood_fill_vars_t *vars;
179 : uint8_t *image;
180 : size_t num_vars, vars_byte_size;
181 :
182 121 : image = NULL;
183 121 : pixels = NULL;
184 121 : vars = NULL;
185 :
186 121 : if (width < 0 || height < 0) {
187 0 : return -1;
188 : }
189 :
190 121 : image = lcalloc((size_t)width, (size_t)height);
191 121 : if (!image) {
192 0 : return -1;
193 : }
194 :
195 121 : pixels = lcalloc((size_t)width * (size_t)height, sizeof(lierre_pixel_t));
196 121 : if (!pixels) {
197 0 : lfree(image);
198 :
199 0 : return -1;
200 : }
201 :
202 121 : num_vars = (size_t)height * 2 / 3;
203 121 : if (num_vars == 0) {
204 0 : num_vars = 1;
205 : }
206 :
207 121 : vars_byte_size = sizeof(flood_fill_vars_t) * num_vars;
208 121 : vars = lmalloc(vars_byte_size);
209 121 : if (!vars) {
210 0 : lfree(image);
211 0 : lfree(pixels);
212 :
213 0 : return -1;
214 : }
215 :
216 121 : decoder->w = width;
217 121 : decoder->h = height;
218 :
219 121 : if (decoder->image) {
220 12 : lfree(decoder->image);
221 : }
222 :
223 121 : decoder->image = image;
224 :
225 121 : if (decoder->pixels) {
226 12 : lfree(decoder->pixels);
227 : }
228 :
229 121 : decoder->pixels = pixels;
230 :
231 121 : if (decoder->flood_fill_vars) {
232 12 : lfree(decoder->flood_fill_vars);
233 : }
234 :
235 121 : decoder->flood_fill_vars = vars;
236 121 : decoder->num_flood_fill_vars = num_vars;
237 :
238 121 : return 0;
239 : }
240 :
241 45 : static inline void *decode_qr_thread(void *arg)
242 : {
243 45 : decode_thread_ctx_t *ctx = (decode_thread_ctx_t *)arg;
244 :
245 45 : extract_qr_code(ctx->decoder, ctx->grid_index, &ctx->code);
246 45 : ctx->err = decode_qr(&ctx->code, &ctx->data);
247 :
248 45 : return NULL;
249 : }
250 :
251 109 : extern decoder_t *lierre_decoder_create(void)
252 : {
253 : decoder_t *decoder;
254 :
255 109 : decoder = lcalloc(1, sizeof(decoder_t));
256 109 : if (!decoder) {
257 0 : return NULL;
258 : }
259 :
260 109 : return decoder;
261 : }
262 :
263 109 : extern void lierre_decoder_destroy(decoder_t *decoder)
264 : {
265 109 : if (!decoder) {
266 0 : return;
267 : }
268 :
269 109 : if (decoder->image) {
270 109 : lfree(decoder->image);
271 : }
272 :
273 109 : if (decoder->pixels) {
274 109 : lfree(decoder->pixels);
275 : }
276 :
277 109 : if (decoder->flood_fill_vars) {
278 109 : lfree(decoder->flood_fill_vars);
279 : }
280 :
281 109 : lfree(decoder);
282 : }
283 :
284 73 : extern lierre_error_t lierre_decoder_process(decoder_t *decoder, const uint8_t *gray_image, int32_t width,
285 : int32_t height, decoder_result_t *result)
286 : {
287 : qr_code_t code;
288 : qr_data_t data;
289 : lierre_error_t err;
290 : uint8_t threshold;
291 : int32_t row, i;
292 :
293 73 : if (!decoder || !gray_image || !result || width <= 0 || height <= 0) {
294 0 : return LIERRE_ERROR_INVALID_PARAMS;
295 : }
296 :
297 73 : if (decoder_resize(decoder, width, height) < 0) {
298 0 : return LIERRE_ERROR_DATA_OVERFLOW;
299 : }
300 :
301 73 : lmemcpy(decoder->image, gray_image, (size_t)width * (size_t)height);
302 :
303 73 : decoder->num_regions = LIERRE_PIXEL_REGION;
304 73 : decoder->num_capstones = 0;
305 73 : decoder->num_grids = 0;
306 :
307 73 : threshold = compute_otsu_threshold(decoder);
308 73 : decoder->threshold = threshold;
309 73 : binarize_image(decoder, threshold);
310 :
311 48069 : for (row = 0; row < height; row++) {
312 47996 : scan_finder_patterns(decoder, (uint32_t)row);
313 : }
314 :
315 291 : for (i = 0; i < decoder->num_capstones; i++) {
316 218 : find_capstone_groups(decoder, i);
317 : }
318 :
319 73 : result->count = 0;
320 :
321 157 : for (i = 0; i < decoder->num_grids && result->count < LIERRE_DECODER_MAX_GRIDS; i++) {
322 84 : extract_qr_code(decoder, i, &code);
323 84 : err = decode_qr(&code, &data);
324 :
325 84 : if (err == LIERRE_ERROR_SUCCESS) {
326 62 : result->codes[result->count].corners[0] = code.corners[0];
327 62 : result->codes[result->count].corners[1] = code.corners[1];
328 62 : result->codes[result->count].corners[2] = code.corners[2];
329 62 : result->codes[result->count].corners[3] = code.corners[3];
330 62 : lmemcpy(result->codes[result->count].payload, data.payload, (size_t)data.payload_len);
331 62 : result->codes[result->count].payload_len = data.payload_len;
332 62 : result->count++;
333 : }
334 : }
335 :
336 73 : return LIERRE_ERROR_SUCCESS;
337 : }
338 :
339 48 : extern lierre_error_t lierre_decoder_process_mt(decoder_t *decoder, const uint8_t *gray_image, int32_t width,
340 : int32_t height, decoder_result_t *result, uint32_t num_threads)
341 : {
342 : lierre_thread_t *threads;
343 : decode_thread_ctx_t *contexts;
344 : uint32_t active_threads, t;
345 : uint8_t threshold;
346 : int32_t row, i;
347 :
348 48 : if (!decoder || !gray_image || !result || width <= 0 || height <= 0) {
349 0 : return LIERRE_ERROR_INVALID_PARAMS;
350 : }
351 :
352 48 : if (num_threads < 1) {
353 0 : num_threads = 1;
354 : }
355 48 : if (num_threads > LIERRE_DECODER_MT_MAX_THREADS) {
356 0 : num_threads = LIERRE_DECODER_MT_MAX_THREADS;
357 : }
358 :
359 48 : if (decoder_resize(decoder, width, height) < 0) {
360 0 : return LIERRE_ERROR_DATA_OVERFLOW;
361 : }
362 :
363 48 : lmemcpy(decoder->image, gray_image, (size_t)width * (size_t)height);
364 :
365 48 : decoder->num_regions = LIERRE_PIXEL_REGION;
366 48 : decoder->num_capstones = 0;
367 48 : decoder->num_grids = 0;
368 :
369 48 : threshold = compute_otsu_threshold(decoder);
370 48 : decoder->threshold = threshold;
371 48 : binarize_image(decoder, threshold);
372 :
373 40993 : for (row = 0; row < height; row++) {
374 40945 : scan_finder_patterns(decoder, (uint32_t)row);
375 : }
376 :
377 196 : for (i = 0; i < decoder->num_capstones; i++) {
378 148 : find_capstone_groups(decoder, i);
379 : }
380 :
381 48 : result->count = 0;
382 :
383 48 : if (decoder->num_grids == 0) {
384 6 : return LIERRE_ERROR_SUCCESS;
385 : }
386 :
387 42 : threads = lmalloc(sizeof(lierre_thread_t) * num_threads);
388 42 : contexts = lmalloc(sizeof(decode_thread_ctx_t) * decoder->num_grids);
389 42 : if (!threads || !contexts) {
390 0 : lfree(threads);
391 0 : lfree(contexts);
392 0 : return LIERRE_ERROR_DATA_OVERFLOW;
393 : }
394 :
395 87 : for (i = 0; i < decoder->num_grids; i++) {
396 45 : contexts[i].decoder = decoder;
397 45 : contexts[i].grid_index = i;
398 45 : contexts[i].err = LIERRE_ERROR_INVALID_PARAMS;
399 : }
400 :
401 42 : i = 0;
402 84 : while (i < decoder->num_grids) {
403 42 : active_threads = 0;
404 :
405 87 : for (t = 0; t < num_threads && i < decoder->num_grids; t++, i++) {
406 45 : lierre_thread_create(&threads[t], decode_qr_thread, &contexts[i]);
407 45 : active_threads++;
408 : }
409 :
410 87 : for (t = 0; t < active_threads; t++) {
411 45 : lierre_thread_join(threads[t], NULL);
412 : }
413 : }
414 :
415 87 : for (i = 0; i < decoder->num_grids && result->count < LIERRE_DECODER_MAX_GRIDS; i++) {
416 45 : if (contexts[i].err == LIERRE_ERROR_SUCCESS) {
417 42 : result->codes[result->count].corners[0] = contexts[i].code.corners[0];
418 42 : result->codes[result->count].corners[1] = contexts[i].code.corners[1];
419 42 : result->codes[result->count].corners[2] = contexts[i].code.corners[2];
420 42 : result->codes[result->count].corners[3] = contexts[i].code.corners[3];
421 42 : lmemcpy(result->codes[result->count].payload, contexts[i].data.payload,
422 : (size_t)contexts[i].data.payload_len);
423 42 : result->codes[result->count].payload_len = contexts[i].data.payload_len;
424 42 : result->count++;
425 : }
426 : }
427 :
428 42 : lfree(threads);
429 42 : lfree(contexts);
430 :
431 42 : return LIERRE_ERROR_SUCCESS;
432 : }
|
