diff options
Diffstat (limited to 'circuitpython/lib/quirc')
26 files changed, 6622 insertions, 0 deletions
diff --git a/circuitpython/lib/quirc/LICENSE b/circuitpython/lib/quirc/LICENSE new file mode 100644 index 0000000..2db5a8f --- /dev/null +++ b/circuitpython/lib/quirc/LICENSE @@ -0,0 +1,19 @@ +quirc -- QR-code recognition library +Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com> + +ISC License +=========== + +Permission to use, copy, modify, and/or distribute this software for +any purpose with or without fee is hereby granted, provided that the +above copyright notice and this permission notice appear in all +copies. + +THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL +WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED +WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE +AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL +DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR +PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER +TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +PERFORMANCE OF THIS SOFTWARE. diff --git a/circuitpython/lib/quirc/Makefile b/circuitpython/lib/quirc/Makefile new file mode 100644 index 0000000..2fc4a14 --- /dev/null +++ b/circuitpython/lib/quirc/Makefile @@ -0,0 +1,103 @@ +# quirc -- QR-code recognition library +# Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com> +# +# Permission to use, copy, modify, and/or distribute this software for any +# purpose with or without fee is hereby granted, provided that the above +# copyright notice and this permission notice appear in all copies. +# +# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES +# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF +# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR +# ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES +# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN +# ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF +# OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + +CC ?= gcc +PREFIX ?= /usr/local +SDL_CFLAGS != pkg-config --cflags sdl +SDL_LIBS != pkg-config --libs sdl + +LIB_VERSION = 1.0 + +CFLAGS ?= -O3 -Wall -fPIC +QUIRC_CFLAGS = -Ilib $(CFLAGS) $(SDL_CFLAGS) +LIB_OBJ = \ + lib/decode.o \ + lib/identify.o \ + lib/quirc.o \ + lib/version_db.o +DEMO_OBJ = \ + demo/camera.o \ + demo/mjpeg.o \ + demo/convert.o +DEMO_UTIL_OBJ = \ + demo/dthash.o \ + demo/demoutil.o + +OPENCV_CFLAGS != pkg-config --cflags opencv4 +OPENCV_LIBS != pkg-config --libs opencv4 +QUIRC_CXXFLAGS = $(QUIRC_CFLAGS) $(OPENCV_CFLAGS) --std=c++17 + +all: libquirc.so qrtest inspect quirc-demo quirc-scanner + +qrtest: tests/dbgutil.o tests/qrtest.o libquirc.a + $(CC) -o $@ tests/dbgutil.o tests/qrtest.o libquirc.a $(LDFLAGS) -lm -ljpeg -lpng + +inspect: tests/dbgutil.o tests/inspect.o libquirc.a + $(CC) -o $@ tests/dbgutil.o tests/inspect.o libquirc.a $(LDFLAGS) -lm -ljpeg -lpng $(SDL_LIBS) -lSDL_gfx + +quirc-demo: $(DEMO_OBJ) $(DEMO_UTIL_OBJ) demo/demo.o libquirc.a + $(CC) -o $@ $(DEMO_OBJ) $(DEMO_UTIL_OBJ) demo/demo.o libquirc.a $(LDFLAGS) -lm -ljpeg $(SDL_LIBS) -lSDL_gfx + +quirc-demo-opencv: $(DEMO_UTIL_OBJ) demo/demo_opencv.o libquirc.a + $(CXX) -o $@ $(DEMO_UTIL_OBJ) demo/demo_opencv.o libquirc.a $(LDFLAGS) -lm $(OPENCV_LIBS) + +quirc-scanner: $(DEMO_OBJ) $(DEMO_UTIL_OBJ) demo/scanner.o libquirc.a + $(CC) -o $@ $(DEMO_OBJ) $(DEMO_UTIL_OBJ) demo/scanner.o libquirc.a $(LDFLAGS) -lm -ljpeg + +libquirc.a: $(LIB_OBJ) + rm -f $@ + ar cru $@ $(LIB_OBJ) + ranlib $@ + +.PHONY: libquirc.so +libquirc.so: libquirc.so.$(LIB_VERSION) + +libquirc.so.$(LIB_VERSION): $(LIB_OBJ) + $(CC) -shared -o $@ $(LIB_OBJ) $(LDFLAGS) -lm + +.c.o: + $(CC) $(QUIRC_CFLAGS) -o $@ -c $< + +.SUFFIXES: .cxx +.cxx.o: + $(CXX) $(QUIRC_CXXFLAGS) -o $@ -c $< + +install: libquirc.a libquirc.so.$(LIB_VERSION) quirc-demo quirc-scanner + install -o root -g root -m 0644 lib/quirc.h $(DESTDIR)$(PREFIX)/include + install -o root -g root -m 0644 libquirc.a $(DESTDIR)$(PREFIX)/lib + install -o root -g root -m 0755 libquirc.so.$(LIB_VERSION) \ + $(DESTDIR)$(PREFIX)/lib + install -o root -g root -m 0755 quirc-demo $(DESTDIR)$(PREFIX)/bin + # install -o root -g root -m 0755 quirc-demo-opencv $(DESTDIR)$(PREFIX)/bin + install -o root -g root -m 0755 quirc-scanner $(DESTDIR)$(PREFIX)/bin + +uninstall: + rm -f $(DESTDIR)$(PREFIX)/include/quirc.h + rm -f $(DESTDIR)$(PREFIX)/lib/libquirc.so.$(LIB_VERSION) + rm -f $(DESTDIR)$(PREFIX)/lib/libquirc.a + rm -f $(DESTDIR)$(PREFIX)/bin/quirc-demo + rm -f $(DESTDIR)$(PREFIX)/bin/quirc-demo-opencv + rm -f $(DESTDIR)$(PREFIX)/bin/quirc-scanner + +clean: + rm -f */*.o + rm -f */*.lo + rm -f libquirc.a + rm -f libquirc.so.$(LIB_VERSION) + rm -f qrtest + rm -f inspect + rm -f quirc-demo + rm -f quirc-demo-opencv + rm -f quirc-scanner diff --git a/circuitpython/lib/quirc/README.md b/circuitpython/lib/quirc/README.md new file mode 100644 index 0000000..c965561 --- /dev/null +++ b/circuitpython/lib/quirc/README.md @@ -0,0 +1,247 @@ +Quirc +===== + +QR codes are a type of high-density matrix barcodes, and quirc is a library for +extracting and decoding them from images. It has several features which make it +a good choice for this purpose: + +* It is fast enough to be used with realtime video: extracting and decoding + from VGA frame takes about 50 ms on a modern x86 core. + +* It has a robust and tolerant recognition algorithm. It can correctly + recognise and decode QR codes which are rotated and/or oblique to the camera. + It can also distinguish and decode multiple codes within the same image. + +* It is easy to use, with a simple API described in a single commented header + file (see below for an overview). + +* It is small and easily embeddable, with no dependencies other than standard C + functions. + +* It has a very small memory footprint: one byte per image pixel, plus a few kB + per decoder object. + +* It uses no global mutable state, and is safe to use in a multithreaded + application. + +* BSD-licensed, with almost no restrictions regarding use and/or modification. + +The distribution comes with, in addition to the library, several test programs. +While the core library is very portable, these programs have some additional +dependencies as documented below. + +### quirc-demo + +This is an real-time demo which requires a camera and a graphical display. The +video stream is displayed on screen as it's received, and any QR codes +recognised are highlighted in the image, with the decoded information both +displayed on the image and printed on stdout. + +This requires: libjpeg, libpng, SDL, V4L2 + +### quirc-demo-opencv + +A demo similar to `quirc-demo`. +But this version uses OpenCV instead of other libraries. + +This requires: OpenCV + +### quirc-scanner + +This program turns your camera into a barcode scanner. It's almost the same as +the `demo` application, but it doesn't display the video stream, and thus +doesn't require a graphical display. + +This requires: libjpeg, V4L2 + +### qrtest + +This test is used to evaluate the performance of library. Given a directory +tree containing a bunch of JPEG images, it will attempt to locate and decode QR +codes in each image. Speed and success statistics are collected and printed on +stdout. + +This requires: libjpeg, libpng + +### inspect + +This test is used for debugging. Given a single JPEG image, it will display a +diagram showing the internal state of the decoder as well as printing +additional information on stdout. + +This requires: libjpeg, libpng, SDL + +Build-time requirements +----------------------- + +### make + +While we are trying to keep our makefiles portable, +it might be incompatible with some versions of make. + +#### GNU make + +Version 4.x and later works. We recommend to use it. + +Version prior to 4.0 doesn't work because it doesn't support `!=`. + +*Note*: macOS's default version of make is GNU make 3.81 as of writing this. + +#### BSD make + +It also works. +You might need to specify the `-r` make option because some of +the default macros like CFLAGS from sys.mk can cause unintended effects. + +Installation +------------ +To build the library and associated demos/tests, type `make`. If you need to +decode "large" image files build with `CFLAGS="-DQUIRC_MAX_REGIONS=65534" make` +instead. Note that this will increase the memory usage, it is discouraged for +low resource devices (i.e. embedded). + +Type `make install` to install the library, header file and camera demos. + +You can specify one or several of the following targets if you don't want, or +are unable to build everything: + +* libquirc.a +* libquirc.so +* qrtest +* inspect +* quirc-scanner +* quirc-demo +* quirc-demo-opencv + +Library use +----------- +All of the library's functionality is exposed through a single header file, +which you should include: + +```C +#include <quirc.h> +``` + +To decode images, you'll need to instantiate a `struct quirc` object, which is +done with the `quirc_new` function. Later, when you no longer need to decode +anything, you should release the allocated memory with `quirc_destroy`: + +```C +struct quirc *qr; + +qr = quirc_new(); +if (!qr) { + perror("Failed to allocate memory"); + abort(); +} + +/* ... */ + +quirc_destroy(qr); +``` + +Having obtained a decoder object, you need to set the image size that you'll be +working with, which is done using `quirc_resize`: + +```C +if (quirc_resize(qr, 640, 480) < 0) { + perror("Failed to allocate video memory"); + abort(); +} +``` + +`quirc_resize` and `quirc_new` are the only library functions which allocate +memory. If you plan to process a series of frames (or a video stream), you +probably want to allocate and size a single decoder and hold onto it to process +each frame. + +Processing frames is done in two stages. The first stage is an +image-recognition stage called identification, which takes a grayscale image +and searches for QR codes. Using `quirc_begin` and `quirc_end`, you can feed a +grayscale image directly into the buffer that `quirc` uses for image +processing: + +```C +uint8_t *image; +int w, h; + +image = quirc_begin(qr, &w, &h); + +/* Fill out the image buffer here. + * image is a pointer to a w*h bytes. + * One byte per pixel, w pixels per line, h lines in the buffer. + */ + +quirc_end(qr); +``` + +Note that `quirc_begin` simply returns a pointer to a previously allocated +buffer. The buffer will contain uninitialized data. After the call to +`quirc_end`, the decoder holds a list of detected QR codes which can be queried +via `quirc_count` and `quirc_extract`. + +At this point, the second stage of processing occurs -- decoding. This is done +via the call to `quirc_decode`, which is not associated with a decoder object. + +```C +int num_codes; +int i; + +/* We've previously fed an image to the decoder via +* quirc_begin/quirc_end. +*/ + +num_codes = quirc_count(qr); +for (i = 0; i < num_codes; i++) { + struct quirc_code code; + struct quirc_data data; + quirc_decode_error_t err; + + quirc_extract(qr, i, &code); + + /* Decoding stage */ + err = quirc_decode(&code, &data); + if (err) + printf("DECODE FAILED: %s\n", quirc_strerror(err)); + else + printf("Data: %s\n", data.payload); +} +``` + +`quirc_code` and `quirc_data` are flat structures which don't need to be +initialized or freed after use. + +In case you also need to support horizontally flipped QR-codes (mirrored +images according to ISO 18004:2015, pages 6 and 62), you can make a second +decode attempt with the flipped image data whenever you get an ECC failure: + +```C + err = quirc_decode(&code, &data); + if (err == QUIRC_ERROR_DATA_ECC) { + quirc_flip(&code); + err = quirc_decode(&code, &data); + } + + if (err) + printf("DECODE FAILED: %s\n", quirc_strerror(err)); + else + printf("Data: %s\n", data.payload); +``` + +Copyright +--------- +Copyright (C) 2010-2012 Daniel Beer <<dlbeer@gmail.com>> + +Permission to use, copy, modify, and/or distribute this software for +any purpose with or without fee is hereby granted, provided that the +above copyright notice and this permission notice appear in all +copies. + +THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL +WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED +WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE +AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL +DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR +PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER +TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR +PERFORMANCE OF THIS SOFTWARE. diff --git a/circuitpython/lib/quirc/demo/camera.c b/circuitpython/lib/quirc/demo/camera.c new file mode 100644 index 0000000..8e8de6b --- /dev/null +++ b/circuitpython/lib/quirc/demo/camera.c @@ -0,0 +1,591 @@ +/* quirc -- QR-code recognition library + * Copyright (C) 2010-2014 Daniel Beer <dlbeer@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <stdint.h> +#include <string.h> +#include <fcntl.h> +#include <errno.h> +#include <sys/types.h> +#include <sys/stat.h> +#include <sys/ioctl.h> +#include <sys/mman.h> +#include <unistd.h> +#ifdef __OpenBSD__ +#include <sys/videoio.h> +#else +#include <linux/videodev2.h> +#endif +#include "camera.h" + +/************************************************************************ + * Fraction arithmetic + */ + +static int gcd(int a, int b) +{ + if (a < 0) + a = -a; + if (b < 0) + b = -b; + + for (;;) { + if (a < b) { + const int t = a; + + a = b; + b = t; + } + + if (!b) + break; + + a %= b; + } + + return a; +} + +static void frac_reduce(const struct v4l2_fract *f, struct v4l2_fract *g) +{ + const int x = gcd(f->numerator, f->denominator); + int n = f->numerator; + int d = f->denominator; + + if (d < 0) { + n = -n; + d = -d; + } + + g->numerator = n / x; + g->denominator = d / x; +} + +static void frac_add(const struct v4l2_fract *a, const struct v4l2_fract *b, + struct v4l2_fract *r) +{ + r->numerator = a->numerator * b->denominator + + b->numerator * b->denominator; + r->denominator = a->denominator * b->denominator; + + frac_reduce(r, r); +} + +static void frac_sub(const struct v4l2_fract *a, const struct v4l2_fract *b, + struct v4l2_fract *r) +{ + r->numerator = a->numerator * b->denominator - + b->numerator * b->denominator; + r->denominator = a->denominator * b->denominator; + + frac_reduce(r, r); +} + +static int frac_cmp(const struct v4l2_fract *a, const struct v4l2_fract *b) +{ + return a->numerator * b->denominator - b->numerator * b->denominator; +} + +static void frac_mul(const struct v4l2_fract *a, const struct v4l2_fract *b, + struct v4l2_fract *r) +{ + r->numerator = a->numerator * b->numerator; + r->denominator = a->denominator * b->denominator; + + frac_reduce(r, r); +} + +static void frac_div(const struct v4l2_fract *a, const struct v4l2_fract *b, + struct v4l2_fract *r) +{ + r->numerator = a->numerator * b->denominator; + r->denominator = a->denominator * b->numerator; + + frac_reduce(r, r); +} + +static int frac_cmp_ref(const struct v4l2_fract *ref, + const struct v4l2_fract *a, + const struct v4l2_fract *b) +{ + struct v4l2_fract da; + struct v4l2_fract db; + + frac_sub(a, ref, &da); + frac_sub(b, ref, &db); + + if (da.numerator < 0) + da.numerator = -da.numerator; + if (db.numerator < 0) + db.numerator = -db.numerator; + + return frac_cmp(&da, &db); +} + +/************************************************************************ + * Parameter searching and choosing + */ + +static camera_format_t map_fmt(uint32_t pf) +{ + if (pf == V4L2_PIX_FMT_YUYV) + return CAMERA_FORMAT_YUYV; + + if (pf == V4L2_PIX_FMT_MJPEG) + return CAMERA_FORMAT_MJPEG; + + return CAMERA_FORMAT_UNKNOWN; +} + +static int find_best_format(int fd, uint32_t *fmt_ret) +{ + struct v4l2_fmtdesc best; + int i = 1; + + memset(&best, 0, sizeof(best)); + best.type = V4L2_BUF_TYPE_VIDEO_CAPTURE; + best.index = 0; + + if (ioctl(fd, VIDIOC_ENUM_FMT, &best) < 0) + return -1; + + for (;;) { + struct v4l2_fmtdesc f; + + memset(&f, 0, sizeof(f)); + f.type = V4L2_BUF_TYPE_VIDEO_CAPTURE; + f.index = ++i; + + if (ioctl(fd, VIDIOC_ENUM_FMT, &f) < 0) + break; + + if (map_fmt(f.pixelformat) > map_fmt(best.pixelformat)) + memcpy(&best, &f, sizeof(best)); + } + + if (fmt_ret) + *fmt_ret = best.pixelformat; + + return 0; +} + +static int step_to_discrete(int min, int max, int step, int target) +{ + int offset; + + if (target < min) + return min; + + if (target > max) + return max; + + offset = (target - min) % step; + if ((offset * 2 > step) && (target + step <= max)) + target += step; + + return target - offset; +} + +static int score_discrete(const struct v4l2_frmsizeenum *f, int w, int h) +{ + const int dw = f->discrete.width - w; + const int dh = f->discrete.height - h; + + return dw * dw + dh * dh; +} + +static int find_best_size(int fd, uint32_t pixel_format, + int target_w, int target_h, + int *ret_w, int *ret_h) +{ + struct v4l2_frmsizeenum best; + int i = 1; + + memset(&best, 0, sizeof(best)); + best.index = 0; + best.pixel_format = pixel_format; + + if (ioctl(fd, VIDIOC_ENUM_FRAMESIZES, &best) < 0) + return -1; + + if (best.type != V4L2_FRMSIZE_TYPE_DISCRETE) { + *ret_w = step_to_discrete(best.stepwise.min_width, + best.stepwise.max_width, + best.stepwise.step_width, + target_w); + *ret_h = step_to_discrete(best.stepwise.min_height, + best.stepwise.max_height, + best.stepwise.step_height, + target_h); + return 0; + } + + for (;;) { + struct v4l2_frmsizeenum f; + + memset(&f, 0, sizeof(f)); + f.index = ++i; + f.pixel_format = pixel_format; + + if (ioctl(fd, VIDIOC_ENUM_FRAMESIZES, &f) < 0) + break; + + if (score_discrete(&f, target_w, target_h) < + score_discrete(&best, target_w, target_h)) + memcpy(&best, &f, sizeof(best)); + } + + *ret_w = best.discrete.width; + *ret_h = best.discrete.height; + + return 0; +} + +static int find_best_rate(int fd, uint32_t pixel_format, + int w, int h, int target_n, int target_d, + int *ret_n, int *ret_d) +{ + const struct v4l2_fract target = { + .numerator = target_n, + .denominator = target_d + }; + struct v4l2_frmivalenum best; + int i = 1; + + memset(&best, 0, sizeof(best)); + best.index = 0; + best.pixel_format = pixel_format; + best.width = w; + best.height = h; + + if (ioctl(fd, VIDIOC_ENUM_FRAMEINTERVALS, &best) < 0) + return -1; + + if (best.type != V4L2_FRMIVAL_TYPE_DISCRETE) { + struct v4l2_fract t; + + if (frac_cmp(&target, &best.stepwise.min) < 0) { + *ret_n = best.stepwise.min.numerator; + *ret_d = best.stepwise.min.denominator; + } + + if (frac_cmp(&target, &best.stepwise.max) > 0) { + *ret_n = best.stepwise.max.numerator; + *ret_d = best.stepwise.max.denominator; + } + + frac_sub(&target, &best.stepwise.min, &t); + frac_div(&t, &best.stepwise.step, &t); + if (t.numerator * 2 >= t.denominator) + t.numerator += t.denominator; + t.numerator /= t.denominator; + t.denominator = 1; + frac_mul(&t, &best.stepwise.step, &t); + frac_add(&t, &best.stepwise.max, &t); + + if (frac_cmp(&t, &best.stepwise.max) > 0) { + *ret_n = best.stepwise.max.numerator; + *ret_d = best.stepwise.max.denominator; + } else { + *ret_n = t.numerator; + *ret_d = t.denominator; + } + + return 0; + } + + for (;;) { + struct v4l2_frmivalenum f; + + memset(&f, 0, sizeof(f)); + f.index = ++i; + f.pixel_format = pixel_format; + f.width = w; + f.height = h; + + if (ioctl(fd, VIDIOC_ENUM_FRAMEINTERVALS, &f) < 0) + break; + + if (frac_cmp_ref(&target, &f.discrete, &best.discrete) < 0) + memcpy(&best, &f, sizeof(best)); + } + + *ret_n = best.discrete.numerator; + *ret_d = best.discrete.denominator; + + return 0; +} + +/************************************************************************ + * Public interface + */ + +void camera_init(struct camera *c) +{ + c->fd = -1; + c->buf_count = 0; + c->s_on = 0; +} + +void camera_destroy(struct camera *c) +{ + camera_close(c); +} + +int camera_open(struct camera *c, const char *path, + int target_w, int target_h, + int tr_n, int tr_d) +{ + struct v4l2_format fmt; + struct v4l2_streamparm parm; + uint32_t pf; + int w, h; + int n, d; + + if (c->fd >= 0) + camera_close(c); + + /* Open device and get basic properties */ + c->fd = open(path, O_RDWR); + if (c->fd < 0) + return -1; + + /* Find a pixel format from the list */ + if (find_best_format(c->fd, &pf) < 0) + goto fail; + + /* Find a frame size */ + if (find_best_size(c->fd, pf, target_w, target_h, &w, &h) < 0) + goto fail; + + /* Find a frame rate */ + if (find_best_rate(c->fd, pf, w, h, tr_n, tr_d, &n, &d) < 0) + goto fail; + + /* Set format */ + memset(&fmt, 0, sizeof(fmt)); + fmt.type = V4L2_BUF_TYPE_VIDEO_CAPTURE; + fmt.fmt.pix.width = w; + fmt.fmt.pix.height = h; + fmt.fmt.pix.pixelformat = pf; + if (ioctl(c->fd, VIDIOC_S_FMT, &fmt) < 0) + goto fail; + + memset(&fmt, 0, sizeof(fmt)); + fmt.type = V4L2_BUF_TYPE_VIDEO_CAPTURE; + if (ioctl(c->fd, VIDIOC_G_FMT, &fmt) < 0) + goto fail; + + /* Set frame interval */ + memset(&parm, 0, sizeof(parm)); + parm.type = V4L2_BUF_TYPE_VIDEO_CAPTURE; + parm.parm.capture.timeperframe.numerator = n; + parm.parm.capture.timeperframe.denominator = d; + if (ioctl(c->fd, VIDIOC_S_PARM, &parm) < 0) + goto fail; + + memset(&parm, 0, sizeof(parm)); + parm.type = V4L2_BUF_TYPE_VIDEO_CAPTURE; + if (ioctl(c->fd, VIDIOC_G_PARM, &parm) < 0) + goto fail; + + c->parms.format = map_fmt(fmt.fmt.pix.pixelformat); + c->parms.width = fmt.fmt.pix.width; + c->parms.height = fmt.fmt.pix.height; + c->parms.pitch_bytes = fmt.fmt.pix.bytesperline; + c->parms.interval_n = parm.parm.capture.timeperframe.numerator; + c->parms.interval_d = parm.parm.capture.timeperframe.denominator; + + return 0; + +fail: + { + const int e = errno; + + close(c->fd); + c->fd = -1; + errno = e; + } + + return -1; +} + +void camera_close(struct camera *c) +{ + camera_off(c); + camera_unmap(c); + + if (c->fd < 0) + return; + + close(c->fd); + c->fd = -1; +} + +int camera_map(struct camera *c, int buf_count) +{ + struct v4l2_requestbuffers reqbuf; + int count; + int i; + + if (buf_count > CAMERA_MAX_BUFFERS) + buf_count = CAMERA_MAX_BUFFERS; + + if (buf_count <= 0) { + errno = EINVAL; + return -1; + } + + if (c->fd < 0) { + errno = EBADF; + return -1; + } + + if (c->buf_count) + camera_unmap(c); + + memset(&reqbuf, 0, sizeof(reqbuf)); + reqbuf.count = buf_count; + reqbuf.type = V4L2_BUF_TYPE_VIDEO_CAPTURE; + reqbuf.memory = V4L2_MEMORY_MMAP; + + if (ioctl(c->fd, VIDIOC_REQBUFS, &reqbuf) < 0) + return -1; + + count = reqbuf.count; + if (count > CAMERA_MAX_BUFFERS) + count = CAMERA_MAX_BUFFERS; + + /* Query all buffers */ + for (i = 0; i < count; i++) { + struct v4l2_buffer buf; + struct camera_buffer *cb = &c->buf_desc[i]; + + memset(&buf, 0, sizeof(buf)); + buf.index = i; + buf.type = V4L2_BUF_TYPE_VIDEO_CAPTURE; + buf.memory = V4L2_MEMORY_MMAP; + if (ioctl(c->fd, VIDIOC_QUERYBUF, &buf) < 0) + return -1; + + cb->offset = buf.m.offset; + cb->size = buf.length; + cb->addr = mmap(NULL, cb->size, PROT_READ, + MAP_SHARED, c->fd, cb->offset); + + if (cb->addr == MAP_FAILED) { + const int save = errno; + + i--; + while (i >= 0) { + cb = &c->buf_desc[i--]; + munmap(cb->addr, cb->size); + } + + errno = save; + return -1; + } + } + + c->buf_count = count; + return 0; +} + +void camera_unmap(struct camera *c) +{ + int i; + + for (i = 0; i < c->buf_count; i++) { + struct camera_buffer *cb = &c->buf_desc[i]; + + munmap(cb->addr, cb->size); + } + + c->buf_count = 0; +} + +int camera_on(struct camera *c) +{ + int type = V4L2_BUF_TYPE_VIDEO_CAPTURE; + + if (c->s_on) + return 0; + + if (c->fd < 0) { + errno = EBADF; + return -1; + } + + if (ioctl(c->fd, VIDIOC_STREAMON, &type) < 0) + return -1; + + c->s_on = 1; + c->s_qc = 0; + c->s_qhead = 0; + return 0; +} + +void camera_off(struct camera *c) +{ + int type = V4L2_BUF_TYPE_VIDEO_CAPTURE; + + if (!c->s_on) + return; + + ioctl(c->fd, VIDIOC_STREAMOFF, &type); + c->s_on = 0; +} + +int camera_enqueue_all(struct camera *c) +{ + while (c->s_qc < c->buf_count) { + struct v4l2_buffer buf; + + memset(&buf, 0, sizeof(buf)); + buf.index = (c->s_qc + c->s_qhead) % c->buf_count; + buf.type = V4L2_BUF_TYPE_VIDEO_CAPTURE; + buf.memory = V4L2_MEMORY_MMAP; + + if (ioctl(c->fd, VIDIOC_QBUF, &buf) < 0) + return -1; + + c->s_qc++; + } + + return 0; +} + +int camera_dequeue_one(struct camera *c) +{ + struct v4l2_buffer buf; + + if (!c->s_qc) { + errno = EINVAL; + return -1; + } + + memset(&buf, 0, sizeof(buf)); + buf.memory = V4L2_MEMORY_MMAP; + buf.type = V4L2_BUF_TYPE_VIDEO_CAPTURE; + + if (ioctl(c->fd, VIDIOC_DQBUF, &buf) < 0) + return -1; + + c->s_qc--; + if (++c->s_qhead >= c->buf_count) + c->s_qhead = 0; + + return 0; +} diff --git a/circuitpython/lib/quirc/demo/camera.h b/circuitpython/lib/quirc/demo/camera.h new file mode 100644 index 0000000..511b5bd --- /dev/null +++ b/circuitpython/lib/quirc/demo/camera.h @@ -0,0 +1,104 @@ +/* quirc -- QR-code recognition library + * Copyright (C) 2010-2014 Daniel Beer <dlbeer@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#ifndef CAMERA_H_ +#define CAMERA_H_ + +#include <stddef.h> + +#define CAMERA_MAX_BUFFERS 32 + +typedef enum { + CAMERA_FORMAT_UNKNOWN = 0, + CAMERA_FORMAT_MJPEG, + CAMERA_FORMAT_YUYV +} camera_format_t; + +struct camera_parms { + camera_format_t format; + int width; + int height; + int pitch_bytes; + int interval_n; + int interval_d; +}; + +struct camera_buffer { + void *addr; + size_t size; + unsigned long offset; +}; + +struct camera { + int fd; + + struct camera_parms parms; + + struct camera_buffer buf_desc[CAMERA_MAX_BUFFERS]; + int buf_count; + + /* Stream state */ + int s_on; + int s_qc; + int s_qhead; +}; + +/* Initialize/destroy a camera. No resources are allocated. */ +void camera_init(struct camera *c); +void camera_destroy(struct camera *c); + +/* Open/close the camera device */ +int camera_open(struct camera *c, const char *path, + int target_w, int target_h, + int tr_n, int tr_d); +void camera_close(struct camera *c); + +static inline int camera_get_fd(const struct camera *c) +{ + return c->fd; +} + +static inline const struct camera_parms *camera_get_parms + (const struct camera *c) +{ + return &c->parms; +} + +/* Map buffers */ +int camera_map(struct camera *c, int buf_count); +void camera_unmap(struct camera *c); + +static inline int camera_get_buf_count(const struct camera *c) +{ + return c->buf_count; +} + +/* Switch streaming on/off */ +int camera_on(struct camera *c); +void camera_off(struct camera *c); + +/* Enqueue/dequeue buffers (count = 0 means enqueue all) */ +int camera_enqueue_all(struct camera *c); +int camera_dequeue_one(struct camera *c); + +/* Fetch the oldest dequeued buffer */ +static inline const struct camera_buffer *camera_get_head + (const struct camera *c) +{ + return &c->buf_desc[(c->s_qhead + c->buf_count - 1) % c->buf_count]; +} + +#endif diff --git a/circuitpython/lib/quirc/demo/convert.c b/circuitpython/lib/quirc/demo/convert.c new file mode 100644 index 0000000..9e6f458 --- /dev/null +++ b/circuitpython/lib/quirc/demo/convert.c @@ -0,0 +1,103 @@ +/* quirc -- QR-code recognition library + * Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include "convert.h" + +#define CHANNEL_CLAMP(dst, tmp, lum, chrom) \ + (tmp) = ((lum) + (chrom)) >> 8; \ + if ((tmp) < 0) \ + (tmp) = 0; \ + if ((tmp) > 255) \ + (tmp) = 255; \ + (dst) = (tmp); + +void yuyv_to_rgb32(const uint8_t *src, int src_pitch, + int w, int h, + uint8_t *dst, int dst_pitch) +{ + int y; + + for (y = 0; y < h; y++) { + int x; + const uint8_t *srow = src + y * src_pitch; + uint8_t *drow = dst + y * dst_pitch; + + for (x = 0; x < w; x += 2) { + /* ITU-R colorspace assumed */ + int y0 = (int)srow[0] * 256; + int y1 = (int)srow[2] * 256; + int cr = (int)srow[3] - 128; + int cb = (int)srow[1] - 128; + int r = cr * 359; + int g = -cb * 88 - 128 * cr; + int b = 454 * cb; + int z; + + CHANNEL_CLAMP(drow[0], z, y0, b); + CHANNEL_CLAMP(drow[1], z, y0, g); + CHANNEL_CLAMP(drow[2], z, y0, r); + CHANNEL_CLAMP(drow[4], z, y1, b); + CHANNEL_CLAMP(drow[5], z, y1, g); + CHANNEL_CLAMP(drow[6], z, y1, r); + + srow += 4; + drow += 8; + } + } +} + +void yuyv_to_luma(const uint8_t *src, int src_pitch, + int w, int h, + uint8_t *dst, int dst_pitch) +{ + int y; + + for (y = 0; y < h; y++) { + int x; + const uint8_t *srow = src + y * src_pitch; + uint8_t *drow = dst + y * dst_pitch; + + for (x = 0; x < w; x += 2) { + *(drow++) = srow[0]; + *(drow++) = srow[2]; + srow += 4; + } + } +} + +void rgb32_to_luma(const uint8_t *src, int src_pitch, + int w, int h, + uint8_t *dst, int dst_pitch) +{ + int y; + + for (y = 0; y < h; y++) { + const uint8_t *rgb32 = src + src_pitch * y; + uint8_t *gray = dst + y * dst_pitch; + int i; + + for (i = 0; i < w; i++) { + /* ITU-R colorspace assumed */ + int r = (int)rgb32[2]; + int g = (int)rgb32[1]; + int b = (int)rgb32[0]; + int sum = r * 59 + g * 150 + b * 29; + + *(gray++) = sum >> 8; + rgb32 += 4; + } + } +} diff --git a/circuitpython/lib/quirc/demo/convert.h b/circuitpython/lib/quirc/demo/convert.h new file mode 100644 index 0000000..ec2a14e --- /dev/null +++ b/circuitpython/lib/quirc/demo/convert.h @@ -0,0 +1,39 @@ +/* quirc -- QR-code recognition library + * Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#ifndef CONVERT_H_ +#define CONVERT_H_ + +#include <stdint.h> + +/* Convert 4:2:2 YUYV format to RGB32 format. The source and destination + * frames are expected to be the same size. + */ +void yuyv_to_rgb32(const uint8_t *src, int src_pitch, + int w, int h, + uint8_t *dst, int dst_pitch); + +/* Extract the luma channel from a 4:2:2 YUYV image. */ +void yuyv_to_luma(const uint8_t *src, int src_pitch, + int w, int h, + uint8_t *dst, int dst_pitch); + +/* Extract the luma channel from an RGB32 image. */ +void rgb32_to_luma(const uint8_t *src, int src_pitch, + int w, int h, + uint8_t *dst, int dst_pitch); + +#endif diff --git a/circuitpython/lib/quirc/demo/demo.c b/circuitpython/lib/quirc/demo/demo.c new file mode 100644 index 0000000..178fde8 --- /dev/null +++ b/circuitpython/lib/quirc/demo/demo.c @@ -0,0 +1,333 @@ +/* quirc -- QR-code recognition library + * Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <unistd.h> +#include <SDL.h> +#include <SDL_gfxPrimitives.h> +#include <quirc.h> +#include <time.h> +#include <getopt.h> + +#include "camera.h" +#include "mjpeg.h" +#include "convert.h" +#include "dthash.h" +#include "demoutil.h" + +/* Collected command-line arguments */ +static const char *camera_path = "/dev/video0"; +static int video_width = 640; +static int video_height = 480; +static int want_frame_rate = 0; +static int want_verbose = 0; +static int printer_timeout = 2; + +static void fat_text(SDL_Surface *screen, int x, int y, const char *text) +{ + int i, j; + + for (i = -1; i <= 1; i++) + for (j = -1; j <= 1; j++) + stringColor(screen, x + i, y + j, text, 0xffffffff); + stringColor(screen, x, y, text, 0x008000ff); +} + +static void fat_text_cent(SDL_Surface *screen, int x, int y, const char *text) +{ + x -= strlen(text) * 4; + + fat_text(screen, x, y, text); +} + +static void draw_qr(SDL_Surface *screen, struct quirc *q, struct dthash *dt) +{ + int count = quirc_count(q); + int i; + + for (i = 0; i < count; i++) { + struct quirc_code code; + struct quirc_data data; + quirc_decode_error_t err; + int j; + int xc = 0; + int yc = 0; + char buf[128]; + + quirc_extract(q, i, &code); + + for (j = 0; j < 4; j++) { + struct quirc_point *a = &code.corners[j]; + struct quirc_point *b = &code.corners[(j + 1) % 4]; + + xc += a->x; + yc += a->y; + lineColor(screen, a->x, a->y, b->x, b->y, 0x008000ff); + } + + xc /= 4; + yc /= 4; + + if (want_verbose) { + snprintf(buf, sizeof(buf), "Code size: %d cells", + code.size); + fat_text_cent(screen, xc, yc - 20, buf); + } + + err = quirc_decode(&code, &data); + + if (err) { + if (want_verbose) + fat_text_cent(screen, xc, yc, + quirc_strerror(err)); + } else { + fat_text_cent(screen, xc, yc, (char *)data.payload); + print_data(&data, dt, want_verbose); + + if (want_verbose) { + snprintf(buf, sizeof(buf), + "Ver: %d, ECC: %c, Mask: %d, Type: %d", + data.version, "MLHQ"[data.ecc_level], + data.mask, data.data_type); + fat_text_cent(screen, xc, yc + 20, buf); + } + } + } +} + +static int main_loop(struct camera *cam, SDL_Surface *screen, + struct quirc *q, struct mjpeg_decoder *mj) +{ + SDL_Event ev; + time_t last_rate = 0; + int frame_count = 0; + char rate_text[64]; + struct dthash dt; + + rate_text[0] = 0; + dthash_init(&dt, printer_timeout); + + for (;;) { + time_t now = time(NULL); + const struct camera_buffer *head; + const struct camera_parms *parms = camera_get_parms(cam); + + if (camera_dequeue_one(cam) < 0) { + perror("camera_dequeue_one"); + return -1; + } + + head = camera_get_head(cam); + + SDL_LockSurface(screen); + switch (parms->format) { + case CAMERA_FORMAT_MJPEG: + mjpeg_decode_rgb32(mj, head->addr, head->size, + screen->pixels, screen->pitch, + screen->w, screen->h); + break; + + case CAMERA_FORMAT_YUYV: + yuyv_to_rgb32(head->addr, parms->width * 2, + parms->width, parms->height, + screen->pixels, screen->pitch); + break; + + default: + fprintf(stderr, "Unknown frame format\n"); + return -1; + } + + if (camera_enqueue_all(cam) < 0) { + perror("camera_enqueue_all"); + return -1; + } + + rgb32_to_luma(screen->pixels, screen->pitch, + screen->w, screen->h, + quirc_begin(q, NULL, NULL), + screen->w); + quirc_end(q); + SDL_UnlockSurface(screen); + + draw_qr(screen, q, &dt); + if (want_frame_rate) + fat_text(screen, 5, 5, rate_text); + SDL_Flip(screen); + + while (SDL_PollEvent(&ev) > 0) { + if (ev.type == SDL_QUIT) + return 0; + + if (ev.type == SDL_KEYDOWN && ev.key.keysym.sym == 'q') + return 0; + } + + if (now != last_rate) { + snprintf(rate_text, sizeof(rate_text), + "Frame rate: %d fps", frame_count); + frame_count = 0; + last_rate = now; + } + + frame_count++; + } +} + +static int run_demo(void) +{ + struct quirc *qr; + struct camera cam; + struct mjpeg_decoder mj; + const struct camera_parms *parms; + SDL_Surface *screen; + + camera_init(&cam); + if (camera_open(&cam, camera_path, video_width, video_height, + 25, 1) < 0) { + perror("camera_open"); + goto fail_qr; + } + + if (camera_map(&cam, 8) < 0) { + perror("camera_map"); + goto fail_qr; + } + + if (camera_on(&cam) < 0) { + perror("camera_on"); + goto fail_qr; + } + + if (camera_enqueue_all(&cam) < 0) { + perror("camera_enqueue_all"); + goto fail_qr; + } + + parms = camera_get_parms(&cam); + + qr = quirc_new(); + if (!qr) { + perror("couldn't allocate QR decoder"); + goto fail_qr; + } + + if (quirc_resize(qr, parms->width, parms->height) < 0) { + perror("couldn't allocate QR buffer"); + goto fail_qr_resize; + } + + if (SDL_Init(SDL_INIT_VIDEO) < 0) { + perror("couldn't init SDL"); + goto fail_sdl_init; + } + + screen = SDL_SetVideoMode(parms->width, parms->height, 32, + SDL_SWSURFACE | SDL_DOUBLEBUF); + if (!screen) { + perror("couldn't init video mode"); + goto fail_video_mode; + } + + mjpeg_init(&mj); + if (main_loop(&cam, screen, qr, &mj) < 0) + goto fail_main_loop; + mjpeg_free(&mj); + + SDL_Quit(); + quirc_destroy(qr); + camera_destroy(&cam); + + return 0; + +fail_main_loop: + mjpeg_free(&mj); +fail_video_mode: + SDL_Quit(); +fail_qr_resize: +fail_sdl_init: + quirc_destroy(qr); +fail_qr: + camera_destroy(&cam); + + return -1; +} + +static void usage(const char *progname) +{ + printf("Usage: %s [options]\n\n" +"Valid options are:\n\n" +" -f Show frame rate on screen.\n" +" -v Show extra data for detected codes.\n" +" -d <device> Specify camera device path.\n" +" -s <WxH> Specify video dimensions.\n" +" -p <timeout> Set printer timeout (seconds).\n" +" --help Show this information.\n" +" --version Show library version information.\n", + progname); +} + +int main(int argc, char **argv) +{ + static const struct option longopts[] = { + {"help", 0, 0, 'H'}, + {"version", 0, 0, 'V'}, + {NULL, 0, 0, 0} + }; + int opt; + + printf("quirc demo\n"); + printf("Copyright (C) 2010-2014 Daniel Beer <dlbeer@gmail.com>\n"); + printf("\n"); + + while ((opt = getopt_long(argc, argv, "d:s:fvg:p:", + longopts, NULL)) >= 0) + switch (opt) { + case 'V': + printf("Library version: %s\n", quirc_version()); + return 0; + + case 'H': + usage(argv[0]); + return 0; + + case 'v': + want_verbose = 1; + break; + + case 'f': + want_frame_rate = 1; + break; + + case 's': + if (parse_size(optarg, &video_width, &video_height) < 0) + return -1; + break; + + case 'p': + printer_timeout = atoi(optarg); + break; + + case 'd': + camera_path = optarg; + break; + + case '?': + fprintf(stderr, "Try --help for usage information\n"); + return -1; + } + + return run_demo(); +} diff --git a/circuitpython/lib/quirc/demo/demo_opencv.cxx b/circuitpython/lib/quirc/demo/demo_opencv.cxx new file mode 100644 index 0000000..d6dbe8b --- /dev/null +++ b/circuitpython/lib/quirc/demo/demo_opencv.cxx @@ -0,0 +1,263 @@ +/* quirc -- QR-code recognition library + * Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <assert.h> +#include <unistd.h> +#include <quirc.h> +#include <time.h> +#include <getopt.h> + +#include <opencv2/videoio.hpp> +#include <opencv2/imgproc.hpp> +#include <opencv2/highgui.hpp> + +using namespace cv; + +#include "camera.h" +#include "convert.h" +#include "dthash.h" +#include "demoutil.h" + +/* Collected command-line arguments */ +static int want_frame_rate = 0; +static int want_verbose = 0; +static int printer_timeout = 2; + +static const int font = FONT_HERSHEY_PLAIN; +static const int thickness = 2; +static const double font_scale = 1.5; +static Scalar blue = Scalar(255, 0, 8); + +static void fat_text(Mat &screen, int x, int y, const char *text) +{ + putText(screen, text, Point(x, y), font, font_scale, blue, thickness); +} + +static void fat_text_cent(Mat &screen, int x, int y, const char *text) +{ + int baseline; + + Size size = getTextSize(text, font, font_scale, thickness, &baseline); + putText(screen, text, Point(x - size.width / 2, y - size.height /2), + font, font_scale, blue, thickness); +} + +static void draw_qr(Mat &screen, struct quirc *q, struct dthash *dt) +{ + int count = quirc_count(q); + int i; + + for (i = 0; i < count; i++) { + struct quirc_code code; + struct quirc_data data; + quirc_decode_error_t err; + int j; + int xc = 0; + int yc = 0; + char buf[128]; + + quirc_extract(q, i, &code); + + for (j = 0; j < 4; j++) { + struct quirc_point *a = &code.corners[j]; + struct quirc_point *b = &code.corners[(j + 1) % 4]; + + xc += a->x; + yc += a->y; + line(screen, Point(a->x, a->y), Point(b->x, b->y), blue, 8); + } + + xc /= 4; + yc /= 4; + + if (want_verbose) { + snprintf(buf, sizeof(buf), "Code size: %d cells", + code.size); + fat_text_cent(screen, xc, yc - 20, buf); + } + + err = quirc_decode(&code, &data); + + if (err) { + if (want_verbose) + fat_text_cent(screen, xc, yc, quirc_strerror(err)); + } else { + fat_text_cent(screen, xc, yc, (const char *)data.payload); + print_data(&data, dt, want_verbose); + + if (want_verbose) { + snprintf(buf, sizeof(buf), + "Ver: %d, ECC: %c, Mask: %d, Type: %d", + data.version, "MLHQ"[data.ecc_level], + data.mask, data.data_type); + fat_text_cent(screen, xc, yc + 20, buf); + } + } + } +} + +static int main_loop(VideoCapture &cap, struct quirc *q) +{ + time_t last_rate = 0; + int frame_count = 0; + char rate_text[64]; + struct dthash dt; + + rate_text[0] = 0; + dthash_init(&dt, printer_timeout); + + Mat frame; + for (;;) { + time_t now = time(NULL); + + cap.read(frame); + if (frame.empty()) { + perror("empty frame"); + return 0; + } + + int w; + int h; + uint8_t *buf = quirc_begin(q, &w, &h); + + /* convert frame into buf */ + assert(frame.cols == w); + assert(frame.rows == h); + Mat gray; + cvtColor(frame, gray, COLOR_BGR2GRAY, 0); + for (int y = 0; y < gray.rows; y++) { + for (int x = 0; x < gray.cols; x++) { + buf[(y * w + x)] = gray.at<uint8_t>(y, x); + } + } + + quirc_end(q); + + draw_qr(frame, q, &dt); + if (want_frame_rate) + fat_text(frame, 20, 20, rate_text); + + imshow("quirc-demo-opencv", frame); + waitKey(5); + + if (now != last_rate) { + snprintf(rate_text, sizeof(rate_text), + "Frame rate: %d fps", frame_count); + frame_count = 0; + last_rate = now; + } + + frame_count++; + } +} + +static int run_demo(void) +{ + struct quirc *qr; + VideoCapture cap(0); + unsigned int width; + unsigned int height; + + if (!cap.isOpened()) { + perror("camera_open"); + goto fail_qr; + } + + width = cap.get(CAP_PROP_FRAME_WIDTH); + height = cap.get(CAP_PROP_FRAME_HEIGHT); + + qr = quirc_new(); + if (!qr) { + perror("couldn't allocate QR decoder"); + goto fail_qr; + } + + if (quirc_resize(qr, width, height) < 0) { + perror("couldn't allocate QR buffer"); + goto fail_qr_resize; + } + + if (main_loop(cap, qr) < 0) { + goto fail_main_loop; + } + + quirc_destroy(qr); + + return 0; + +fail_main_loop: +fail_qr_resize: + quirc_destroy(qr); +fail_qr: + + return -1; +} + +static void usage(const char *progname) +{ + printf("Usage: %s [options]\n\n" +"Valid options are:\n\n" +" -f Show frame rate on screen.\n" +" -v Show extra data for detected codes.\n" +" -p <timeout> Set printer timeout (seconds).\n" +" --help Show this information.\n" +" --version Show library version information.\n", + progname); +} + +int main(int argc, char **argv) +{ + static const struct option longopts[] = { + {"help", 0, 0, 'H'}, + {"version", 0, 0, 'V'}, + {NULL, 0, 0, 0} + }; + int opt; + + printf("quirc demo with OpenCV\n"); + printf("Copyright (C) 2010-2014 Daniel Beer <dlbeer@gmail.com>\n"); + printf("\n"); + + while ((opt = getopt_long(argc, argv, "fvg:p:", + longopts, NULL)) >= 0) + switch (opt) { + case 'V': + printf("Library version: %s\n", quirc_version()); + return 0; + + case 'H': + usage(argv[0]); + return 0; + + case 'v': + want_verbose = 1; + break; + + case 'f': + want_frame_rate = 1; + break; + + case 'p': + printer_timeout = atoi(optarg); + break; + + case '?': + fprintf(stderr, "Try --help for usage information\n"); + return -1; + } + + return run_demo(); +} diff --git a/circuitpython/lib/quirc/demo/demoutil.c b/circuitpython/lib/quirc/demo/demoutil.c new file mode 100644 index 0000000..857247a --- /dev/null +++ b/circuitpython/lib/quirc/demo/demoutil.c @@ -0,0 +1,71 @@ +/* quirc -- QR-code recognition library + * Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <stdio.h> +#include <ctype.h> + +#include "demoutil.h" + +void print_data(const struct quirc_data *data, struct dthash *dt, + int want_verbose) +{ + if (dthash_seen(dt, data)) + return; + + printf("==> %s\n", data->payload); + + if (want_verbose) + printf(" Version: %d, ECC: %c, Mask: %d, Type: %d\n\n", + data->version, "MLHQ"[data->ecc_level], + data->mask, data->data_type); +} + +int parse_size(const char *text, int *video_width, int *video_height) +{ + int state = 0; + int w = 0, h = 0; + int i; + + for (i = 0; text[i]; i++) { + if (text[i] == 'x' || text[i] == 'X') { + if (state == 0) { + state = 1; + } else { + fprintf(stderr, "parse_size: expected WxH\n"); + return -1; + } + } else if (isdigit(text[i])) { + if (state == 0) + w = w * 10 + text[i] - '0'; + else + h = h * 10 + text[i] - '0'; + } else { + fprintf(stderr, "Invalid character in size: %c\n", + text[i]); + return -1; + } + } + + if (w <= 0 || w >= 10000 || h <= 0 || h >= 10000) { + fprintf(stderr, "Invalid size: %dx%d\n", w, h); + return -1; + } + + *video_width = w; + *video_height = h; + + return 0; +} diff --git a/circuitpython/lib/quirc/demo/demoutil.h b/circuitpython/lib/quirc/demo/demoutil.h new file mode 100644 index 0000000..888eddd --- /dev/null +++ b/circuitpython/lib/quirc/demo/demoutil.h @@ -0,0 +1,42 @@ +/* quirc -- QR-code recognition library + * Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#ifndef DEMOUTIL_H_ +#define DEMOUTIL_H_ + +#include "dthash.h" +#include "quirc.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/* Check if we've seen the given code, and if not, print it on stdout. + * Include version info if requested. + */ +void print_data(const struct quirc_data *data, struct dthash *dt, + int want_verbose); + +/* Parse a string of the form "WxH" and return width and height as + * integers. Returns 0 on success or -1 if a parser error occurs. + */ +int parse_size(const char *text, int *video_width, int *video_height); + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/circuitpython/lib/quirc/demo/dthash.c b/circuitpython/lib/quirc/demo/dthash.c new file mode 100644 index 0000000..888dc1f --- /dev/null +++ b/circuitpython/lib/quirc/demo/dthash.c @@ -0,0 +1,139 @@ +/* quirc -- QR-code recognition library + * Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <string.h> +#include "dthash.h" + +static const uint32_t crc32_tab[] = { + 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, + 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988, + 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2, + 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, + 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9, + 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172, + 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c, + 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59, + 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, + 0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, + 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106, + 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433, + 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, + 0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, + 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950, + 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65, + 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7, + 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0, + 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa, + 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f, + 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81, + 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a, + 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84, + 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, + 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb, + 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc, + 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e, + 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b, + 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, + 0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, + 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28, + 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d, + 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f, + 0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, + 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242, + 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777, + 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69, + 0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2, + 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, + 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9, + 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693, + 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94, + 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d +}; + +static uint32_t calc_crc(uint32_t crc, const uint8_t *buf, int len) +{ + while (len--) { + crc = crc32_tab[(crc ^ *buf) & 0xff] ^ (crc >> 8); + buf++; + } + + return crc; +} + +static uint32_t code_hash(const struct quirc_data *data) +{ + uint8_t extra[4] = {data->version, data->ecc_level, + data->mask, data->data_type}; + uint32_t crc = calc_crc(0xffffffff, extra, 4); + + return calc_crc(crc, data->payload, data->payload_len); +} + +static void flush_old(struct dthash *d, time_t now) +{ + int i; + + for (i = 0; i < d->count; i++) { + struct dthash_code *c = &d->codes[i]; + + if (c->when + d->timeout <= now) { + if (i + 1 < d->count) + memcpy(c, &d->codes[d->count - 1], sizeof(*c)); + d->count--; + } + } +} + +void dthash_init(struct dthash *d, int timeout) +{ + d->count = 0; + d->timeout = timeout; +} + +int dthash_seen(struct dthash *d, const struct quirc_data *data) +{ + time_t now = time(NULL); + uint32_t hash = code_hash(data); + struct dthash_code *c; + int i; + + flush_old(d, now); + + /* If the code is already seen, update its timestamp */ + for (i = 0; i < d->count; i++) { + c = &d->codes[i]; + if (c->hash == hash) { + c->when = now; + return 1; + } + } + + /* Otherwise, find a place to put it. If necessary, push the + * oldset code out of the table. + */ + if (d->count + 1 < DTHASH_MAX_CODES) { + c = &d->codes[d->count++]; + } else { + c = &d->codes[0]; + for (i = 1; i < d->count; i++) + if (d->codes[i].when < c->when) + c = &d->codes[i]; + } + + c->hash = hash; + c->when = now; + return 0; +} diff --git a/circuitpython/lib/quirc/demo/dthash.h b/circuitpython/lib/quirc/demo/dthash.h new file mode 100644 index 0000000..431db1e --- /dev/null +++ b/circuitpython/lib/quirc/demo/dthash.h @@ -0,0 +1,61 @@ +/* quirc -- QR-code recognition library + * Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#ifndef DTHASH_H_ +#define DTHASH_H_ + +#include <stdint.h> +#include <time.h> +#include "quirc.h" + +/* Detector hash. + * + * This structure keeps track of codes that have been seen within the + * last N seconds, and allows us to print out codes at a reasonable + * rate as we see them. + */ +#define DTHASH_MAX_CODES 32 + +struct dthash_code { + uint32_t hash; + time_t when; +}; + +struct dthash { + struct dthash_code codes[DTHASH_MAX_CODES]; + int count; + int timeout; +}; + +#ifdef __cplusplus +extern "C" { +#endif + +/* Initialise a detector hash with the given timeout. */ +void dthash_init(struct dthash *d, int timeout); + +/* When a code is discovered, this function should be called to see if + * it should be printed. The hash will record having seen the code, and + * return non-zero if it's the first time we've seen it within the + * configured timeout period. + */ +int dthash_seen(struct dthash *d, const struct quirc_data *data); + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/circuitpython/lib/quirc/demo/mjpeg.c b/circuitpython/lib/quirc/demo/mjpeg.c new file mode 100644 index 0000000..09d2197 --- /dev/null +++ b/circuitpython/lib/quirc/demo/mjpeg.c @@ -0,0 +1,284 @@ +/* quirc -- QR-code recognition library + * Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <setjmp.h> +#include <jpeglib.h> +#include <assert.h> +#include "mjpeg.h" + +struct huffman_table { + uint8_t bits[17]; + uint8_t huffval[256]; +}; + +static const struct huffman_table dc_lum = { + .bits = { + 0x00, 0x00, 0x01, 0x05, 0x01, 0x01, 0x01, 0x01, + 0x01, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00 + }, + .huffval = { + 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, + 0x08, 0x09, 0x0a, 0x0b + } +}; + +static const struct huffman_table ac_lum = { + .bits = { + 0x00, 0x00, 0x02, 0x01, 0x03, 0x03, 0x02, 0x04, + 0x03, 0x05, 0x05, 0x04, 0x04, 0x00, 0x00, 0x01, + 0x7d + }, + .huffval = { + 0x01, 0x02, 0x03, 0x00, 0x04, 0x11, 0x05, 0x12, + 0x21, 0x31, 0x41, 0x06, 0x13, 0x51, 0x61, 0x07, + 0x22, 0x71, 0x14, 0x32, 0x81, 0x91, 0xa1, 0x08, + 0x23, 0x42, 0xb1, 0xc1, 0x15, 0x52, 0xd1, 0xf0, + 0x24, 0x33, 0x62, 0x72, 0x82, 0x09, 0x0a, 0x16, + 0x17, 0x18, 0x19, 0x1a, 0x25, 0x26, 0x27, 0x28, + 0x29, 0x2a, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, + 0x3a, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, + 0x4a, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, 0x59, + 0x5a, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, + 0x6a, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, 0x79, + 0x7a, 0x83, 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, + 0x8a, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 0x98, + 0x99, 0x9a, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7, + 0xa8, 0xa9, 0xaa, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, + 0xb7, 0xb8, 0xb9, 0xba, 0xc2, 0xc3, 0xc4, 0xc5, + 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xd2, 0xd3, 0xd4, + 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, 0xe1, 0xe2, + 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 0xe8, 0xe9, 0xea, + 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, + 0xf9, 0xfa + } +}; + +static const struct huffman_table dc_chroma = { + .bits = { + 0x00, 0x00, 0x03, 0x01, 0x01, 0x01, 0x01, 0x01, + 0x01, 0x01, 0x01, 0x01, 0x00, 0x00, 0x00, 0x00, + 0x00 + }, + .huffval = { + 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, + 0x08, 0x09, 0x0a, 0x0b + } +}; + +static const struct huffman_table ac_chroma = { + .bits = { + 0x00, 0x00, 0x02, 0x01, 0x02, 0x04, 0x04, 0x03, + 0x04, 0x07, 0x05, 0x04, 0x04, 0x00, 0x01, 0x02, + 0x77 + }, + .huffval = { + 0x00, 0x01, 0x02, 0x03, 0x11, 0x04, 0x05, 0x21, + 0x31, 0x06, 0x12, 0x41, 0x51, 0x07, 0x61, 0x71, + 0x13, 0x22, 0x32, 0x81, 0x08, 0x14, 0x42, 0x91, + 0xa1, 0xb1, 0xc1, 0x09, 0x23, 0x33, 0x52, 0xf0, + 0x15, 0x62, 0x72, 0xd1, 0x0a, 0x16, 0x24, 0x34, + 0xe1, 0x25, 0xf1, 0x17, 0x18, 0x19, 0x1a, 0x26, + 0x27, 0x28, 0x29, 0x2a, 0x35, 0x36, 0x37, 0x38, + 0x39, 0x3a, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, + 0x49, 0x4a, 0x53, 0x54, 0x55, 0x56, 0x57, 0x58, + 0x59, 0x5a, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, + 0x69, 0x6a, 0x73, 0x74, 0x75, 0x76, 0x77, 0x78, + 0x79, 0x7a, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, + 0x88, 0x89, 0x8a, 0x92, 0x93, 0x94, 0x95, 0x96, + 0x97, 0x98, 0x99, 0x9a, 0xa2, 0xa3, 0xa4, 0xa5, + 0xa6, 0xa7, 0xa8, 0xa9, 0xaa, 0xb2, 0xb3, 0xb4, + 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 0xc2, 0xc3, + 0xc4, 0xc5, 0xc6, 0xc7, 0xc8, 0xc9, 0xca, 0xd2, + 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9, 0xda, + 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 0xe8, 0xe9, + 0xea, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, + 0xf9, 0xfa + } +}; + +static void init_source(j_decompress_ptr cinfo) +{ +} + +static boolean fill_input_buffer(j_decompress_ptr cinfo) +{ + static const uint8_t eoi_marker[] = {0xff, 0xd9}; + + cinfo->src->next_input_byte = eoi_marker; + cinfo->src->bytes_in_buffer = 2; + + return TRUE; +} + +static void skip_input_data(j_decompress_ptr cinfo, long num_bytes) +{ + if (num_bytes < 0) + return; + if (num_bytes > cinfo->src->bytes_in_buffer) + num_bytes = cinfo->src->bytes_in_buffer; + + cinfo->src->bytes_in_buffer -= num_bytes; + cinfo->src->next_input_byte += num_bytes; +} + +static void term_source(j_decompress_ptr cinfo) +{ +} + +struct my_jpeg_error { + struct jpeg_error_mgr base; + jmp_buf env; +}; + +static void my_output_message(struct jpeg_common_struct *com) +{ + struct mjpeg_decoder *mj = (struct mjpeg_decoder *)com->err; + char buf[JMSG_LENGTH_MAX]; + + mj->err.format_message(com, buf); + fprintf(stderr, "MJPEG error: %s\n", buf); +} + +static void my_error_exit(struct jpeg_common_struct *com) +{ + struct mjpeg_decoder *mj = (struct mjpeg_decoder *)com->err; + + my_output_message(com); + longjmp(mj->env, 0); +} + +static void setup_table(struct jpeg_decompress_struct *jpeg, + JHUFF_TBL **tbl_ptr, const struct huffman_table *tab) +{ + assert (*tbl_ptr == NULL); + + *tbl_ptr = jpeg_alloc_huff_table((j_common_ptr)jpeg); + memcpy((*tbl_ptr)->bits, tab->bits, 17); + memcpy((*tbl_ptr)->huffval, tab->huffval, 256); +} + +void mjpeg_init(struct mjpeg_decoder *mj) +{ + memset(mj, 0, sizeof(*mj)); + + /* Set up error management */ + mj->dinfo.err = jpeg_std_error(&mj->err); + mj->err.error_exit = my_error_exit; + mj->err.output_message = my_output_message; + + mj->src.init_source = init_source; + mj->src.fill_input_buffer = fill_input_buffer; + mj->src.skip_input_data = skip_input_data; + mj->src.resync_to_restart = jpeg_resync_to_restart; + mj->src.term_source = term_source; + + jpeg_create_decompress(&mj->dinfo); + mj->dinfo.src = &mj->src; + mj->dinfo.err = &mj->err; + + setup_table(&mj->dinfo, &mj->dinfo.dc_huff_tbl_ptrs[0], &dc_lum); + setup_table(&mj->dinfo, &mj->dinfo.ac_huff_tbl_ptrs[0], &ac_lum); + setup_table(&mj->dinfo, &mj->dinfo.dc_huff_tbl_ptrs[1], &dc_chroma); + setup_table(&mj->dinfo, &mj->dinfo.ac_huff_tbl_ptrs[1], &ac_chroma); +} + +void mjpeg_free(struct mjpeg_decoder *mj) +{ + jpeg_destroy_decompress(&mj->dinfo); +} + +int mjpeg_decode_rgb32(struct mjpeg_decoder *mj, + const uint8_t *data, int datalen, + uint8_t *out, int pitch, int max_w, int max_h) +{ + if (setjmp(mj->env)) + return -1; + + mj->dinfo.src->bytes_in_buffer = datalen; + mj->dinfo.src->next_input_byte = data; + + jpeg_read_header(&mj->dinfo, TRUE); + mj->dinfo.output_components = 3; + mj->dinfo.out_color_space = JCS_RGB; + jpeg_start_decompress(&mj->dinfo); + + if (mj->dinfo.image_height > max_h || + mj->dinfo.image_width > max_w) { + fprintf(stderr, "MJPEG: frame too big\n"); + return -1; + } + + uint8_t *rgb = calloc(mj->dinfo.image_width, 3); + if (!rgb) { + fprintf(stderr, "memory allocation failed\n"); + return -1; + } + while (mj->dinfo.output_scanline < mj->dinfo.image_height) { + uint8_t *scr = out + pitch * mj->dinfo.output_scanline; + uint8_t *output = rgb; + int i; + + jpeg_read_scanlines(&mj->dinfo, &output, 1); + for (i = 0; i < mj->dinfo.image_width; i++) { + scr[0] = output[2]; + scr[1] = output[1]; + scr[2] = output[0]; + scr += 4; + output += 3; + } + } + free(rgb); + + jpeg_finish_decompress(&mj->dinfo); + + return 0; +} + +int mjpeg_decode_gray(struct mjpeg_decoder *mj, + const uint8_t *data, int datalen, + uint8_t *out, int pitch, int max_w, int max_h) +{ + if (setjmp(mj->env)) + return -1; + + mj->dinfo.src->bytes_in_buffer = datalen; + mj->dinfo.src->next_input_byte = data; + + jpeg_read_header(&mj->dinfo, TRUE); + mj->dinfo.output_components = 1; + mj->dinfo.out_color_space = JCS_GRAYSCALE; + jpeg_start_decompress(&mj->dinfo); + + if (mj->dinfo.image_height > max_h || + mj->dinfo.image_width > max_w) { + fprintf(stderr, "MJPEG: frame too big\n"); + return -1; + } + + while (mj->dinfo.output_scanline < mj->dinfo.image_height) { + uint8_t *scr = out + pitch * mj->dinfo.output_scanline; + + jpeg_read_scanlines(&mj->dinfo, &scr, 1); + } + + jpeg_finish_decompress(&mj->dinfo); + + return 0; +} diff --git a/circuitpython/lib/quirc/demo/mjpeg.h b/circuitpython/lib/quirc/demo/mjpeg.h new file mode 100644 index 0000000..caac855 --- /dev/null +++ b/circuitpython/lib/quirc/demo/mjpeg.h @@ -0,0 +1,54 @@ +/* quirc -- QR-code recognition library + * Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#ifndef MJPEG_H_ +#define MJPEG_H_ + +#include <stdint.h> +#include <stdio.h> +#include <jpeglib.h> +#include <setjmp.h> + +struct mjpeg_decoder { + /* The error manager must be the first item in this struct */ + struct jpeg_error_mgr err; + struct jpeg_decompress_struct dinfo; + struct jpeg_source_mgr src; + jmp_buf env; +}; + +/* Construct an MJPEG decoder. */ +void mjpeg_init(struct mjpeg_decoder *mj); + +/* Free any memory allocated while decoding MJPEG frames. */ +void mjpeg_free(struct mjpeg_decoder *mj); + +/* Decode a single MJPEG image to the buffer given, in RGB format. + * Returns 0 on success, -1 if an error occurs (bad data, or image too + * big for buffer). + */ +int mjpeg_decode_rgb32(struct mjpeg_decoder *mj, + const uint8_t *data, int datalen, + uint8_t *out, int pitch, int max_w, int max_h); + +/* Decode a single MJPEG image to the buffer given in 8-bit grayscale. + * Returns 0 on success, -1 if an error occurs. + */ +int mjpeg_decode_gray(struct mjpeg_decoder *mj, + const uint8_t *data, int datalen, + uint8_t *out, int pitch, int max_w, int max_h); + +#endif diff --git a/circuitpython/lib/quirc/demo/scanner.c b/circuitpython/lib/quirc/demo/scanner.c new file mode 100644 index 0000000..7c6c38e --- /dev/null +++ b/circuitpython/lib/quirc/demo/scanner.c @@ -0,0 +1,214 @@ +/* quirc -- QR-code recognition library + * Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <stdlib.h> +#include <ctype.h> +#include <unistd.h> +#include <quirc.h> +#include <time.h> +#include <getopt.h> + +#include "camera.h" +#include "mjpeg.h" +#include "convert.h" +#include "dthash.h" +#include "demoutil.h" + +/* Collected command-line arguments */ +static const char *camera_path = "/dev/video0"; +static int video_width = 640; +static int video_height = 480; +static int want_verbose = 0; +static int printer_timeout = 2; + +static int main_loop(struct camera *cam, + struct quirc *q, struct mjpeg_decoder *mj) +{ + struct dthash dt; + + dthash_init(&dt, printer_timeout); + + for (;;) { + int w, h; + int i, count; + uint8_t *buf = quirc_begin(q, &w, &h); + const struct camera_buffer *head; + const struct camera_parms *parms = camera_get_parms(cam); + + if (camera_dequeue_one(cam) < 0) { + perror("camera_dequeue_one"); + return -1; + } + + head = camera_get_head(cam); + + switch (parms->format) { + case CAMERA_FORMAT_MJPEG: + mjpeg_decode_gray(mj, head->addr, head->size, + buf, w, w, h); + break; + + case CAMERA_FORMAT_YUYV: + yuyv_to_luma(head->addr, w * 2, w, h, buf, w); + break; + + default: + fprintf(stderr, "Unknown frame format\n"); + return -1; + } + + if (camera_enqueue_all(cam) < 0) { + perror("camera_enqueue_all"); + return -1; + } + + quirc_end(q); + + count = quirc_count(q); + for (i = 0; i < count; i++) { + struct quirc_code code; + struct quirc_data data; + + quirc_extract(q, i, &code); + if (!quirc_decode(&code, &data)) + print_data(&data, &dt, want_verbose); + } + } +} + +static int run_scanner(void) +{ + struct quirc *qr; + struct camera cam; + struct mjpeg_decoder mj; + const struct camera_parms *parms; + + camera_init(&cam); + if (camera_open(&cam, camera_path, video_width, video_height, + 25, 1) < 0) { + perror("camera_open"); + goto fail_qr; + } + + if (camera_map(&cam, 8) < 0) { + perror("camera_map"); + goto fail_qr; + } + + if (camera_on(&cam) < 0) { + perror("camera_on"); + goto fail_qr; + } + + if (camera_enqueue_all(&cam) < 0) { + perror("camera_enqueue_all"); + goto fail_qr; + } + + parms = camera_get_parms(&cam); + + qr = quirc_new(); + if (!qr) { + perror("couldn't allocate QR decoder"); + goto fail_qr; + } + + if (quirc_resize(qr, parms->width, parms->height) < 0) { + perror("couldn't allocate QR buffer"); + goto fail_qr_resize; + } + + mjpeg_init(&mj); + if (main_loop(&cam, qr, &mj) < 0) + goto fail_main_loop; + mjpeg_free(&mj); + + quirc_destroy(qr); + camera_destroy(&cam); + + return 0; + +fail_main_loop: + mjpeg_free(&mj); +fail_qr_resize: + quirc_destroy(qr); +fail_qr: + camera_destroy(&cam); + + return -1; +} + +static void usage(const char *progname) +{ + printf("Usage: %s [options]\n\n" +"Valid options are:\n\n" +" -v Show extra data for detected codes.\n" +" -d <device> Specify camera device path.\n" +" -s <WxH> Specify video dimensions.\n" +" -p <timeout> Set printer timeout (seconds).\n" +" --help Show this information.\n" +" --version Show library version information.\n", + progname); +} + +int main(int argc, char **argv) +{ + static const struct option longopts[] = { + {"help", 0, 0, 'H'}, + {"version", 0, 0, 'V'}, + {NULL, 0, 0, 0} + }; + int opt; + + printf("quirc scanner demo\n"); + printf("Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com>\n"); + printf("\n"); + + while ((opt = getopt_long(argc, argv, "d:s:vg:p:", + longopts, NULL)) >= 0) + switch (opt) { + case 'V': + printf("Library version: %s\n", quirc_version()); + return 0; + + case 'H': + usage(argv[0]); + return 0; + + case 'v': + want_verbose = 1; + break; + + case 's': + if (parse_size(optarg, &video_width, &video_height) < 0) + return -1; + break; + + case 'p': + printer_timeout = atoi(optarg); + break; + + case 'd': + camera_path = optarg; + break; + + case '?': + fprintf(stderr, "Try --help for usage information\n"); + return -1; + } + + return run_scanner(); +} diff --git a/circuitpython/lib/quirc/lib/decode.c b/circuitpython/lib/quirc/lib/decode.c new file mode 100644 index 0000000..d5cf889 --- /dev/null +++ b/circuitpython/lib/quirc/lib/decode.c @@ -0,0 +1,978 @@ +/* quirc -- QR-code recognition library + * Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include "quirc_internal.h" + +#include <string.h> +#include <stdlib.h> + +#define MAX_POLY 64 + +/************************************************************************ + * Galois fields + */ + +struct galois_field { + int p; + const uint8_t *log; + const uint8_t *exp; +}; + +static const uint8_t gf16_exp[16] = { + 0x01, 0x02, 0x04, 0x08, 0x03, 0x06, 0x0c, 0x0b, + 0x05, 0x0a, 0x07, 0x0e, 0x0f, 0x0d, 0x09, 0x01 +}; + +static const uint8_t gf16_log[16] = { + 0x00, 0x0f, 0x01, 0x04, 0x02, 0x08, 0x05, 0x0a, + 0x03, 0x0e, 0x09, 0x07, 0x06, 0x0d, 0x0b, 0x0c +}; + +static const struct galois_field gf16 = { + .p = 15, + .log = gf16_log, + .exp = gf16_exp +}; + +static const uint8_t gf256_exp[256] = { + 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, + 0x1d, 0x3a, 0x74, 0xe8, 0xcd, 0x87, 0x13, 0x26, + 0x4c, 0x98, 0x2d, 0x5a, 0xb4, 0x75, 0xea, 0xc9, + 0x8f, 0x03, 0x06, 0x0c, 0x18, 0x30, 0x60, 0xc0, + 0x9d, 0x27, 0x4e, 0x9c, 0x25, 0x4a, 0x94, 0x35, + 0x6a, 0xd4, 0xb5, 0x77, 0xee, 0xc1, 0x9f, 0x23, + 0x46, 0x8c, 0x05, 0x0a, 0x14, 0x28, 0x50, 0xa0, + 0x5d, 0xba, 0x69, 0xd2, 0xb9, 0x6f, 0xde, 0xa1, + 0x5f, 0xbe, 0x61, 0xc2, 0x99, 0x2f, 0x5e, 0xbc, + 0x65, 0xca, 0x89, 0x0f, 0x1e, 0x3c, 0x78, 0xf0, + 0xfd, 0xe7, 0xd3, 0xbb, 0x6b, 0xd6, 0xb1, 0x7f, + 0xfe, 0xe1, 0xdf, 0xa3, 0x5b, 0xb6, 0x71, 0xe2, + 0xd9, 0xaf, 0x43, 0x86, 0x11, 0x22, 0x44, 0x88, + 0x0d, 0x1a, 0x34, 0x68, 0xd0, 0xbd, 0x67, 0xce, + 0x81, 0x1f, 0x3e, 0x7c, 0xf8, 0xed, 0xc7, 0x93, + 0x3b, 0x76, 0xec, 0xc5, 0x97, 0x33, 0x66, 0xcc, + 0x85, 0x17, 0x2e, 0x5c, 0xb8, 0x6d, 0xda, 0xa9, + 0x4f, 0x9e, 0x21, 0x42, 0x84, 0x15, 0x2a, 0x54, + 0xa8, 0x4d, 0x9a, 0x29, 0x52, 0xa4, 0x55, 0xaa, + 0x49, 0x92, 0x39, 0x72, 0xe4, 0xd5, 0xb7, 0x73, + 0xe6, 0xd1, 0xbf, 0x63, 0xc6, 0x91, 0x3f, 0x7e, + 0xfc, 0xe5, 0xd7, 0xb3, 0x7b, 0xf6, 0xf1, 0xff, + 0xe3, 0xdb, 0xab, 0x4b, 0x96, 0x31, 0x62, 0xc4, + 0x95, 0x37, 0x6e, 0xdc, 0xa5, 0x57, 0xae, 0x41, + 0x82, 0x19, 0x32, 0x64, 0xc8, 0x8d, 0x07, 0x0e, + 0x1c, 0x38, 0x70, 0xe0, 0xdd, 0xa7, 0x53, 0xa6, + 0x51, 0xa2, 0x59, 0xb2, 0x79, 0xf2, 0xf9, 0xef, + 0xc3, 0x9b, 0x2b, 0x56, 0xac, 0x45, 0x8a, 0x09, + 0x12, 0x24, 0x48, 0x90, 0x3d, 0x7a, 0xf4, 0xf5, + 0xf7, 0xf3, 0xfb, 0xeb, 0xcb, 0x8b, 0x0b, 0x16, + 0x2c, 0x58, 0xb0, 0x7d, 0xfa, 0xe9, 0xcf, 0x83, + 0x1b, 0x36, 0x6c, 0xd8, 0xad, 0x47, 0x8e, 0x01 +}; + +static const uint8_t gf256_log[256] = { + 0x00, 0xff, 0x01, 0x19, 0x02, 0x32, 0x1a, 0xc6, + 0x03, 0xdf, 0x33, 0xee, 0x1b, 0x68, 0xc7, 0x4b, + 0x04, 0x64, 0xe0, 0x0e, 0x34, 0x8d, 0xef, 0x81, + 0x1c, 0xc1, 0x69, 0xf8, 0xc8, 0x08, 0x4c, 0x71, + 0x05, 0x8a, 0x65, 0x2f, 0xe1, 0x24, 0x0f, 0x21, + 0x35, 0x93, 0x8e, 0xda, 0xf0, 0x12, 0x82, 0x45, + 0x1d, 0xb5, 0xc2, 0x7d, 0x6a, 0x27, 0xf9, 0xb9, + 0xc9, 0x9a, 0x09, 0x78, 0x4d, 0xe4, 0x72, 0xa6, + 0x06, 0xbf, 0x8b, 0x62, 0x66, 0xdd, 0x30, 0xfd, + 0xe2, 0x98, 0x25, 0xb3, 0x10, 0x91, 0x22, 0x88, + 0x36, 0xd0, 0x94, 0xce, 0x8f, 0x96, 0xdb, 0xbd, + 0xf1, 0xd2, 0x13, 0x5c, 0x83, 0x38, 0x46, 0x40, + 0x1e, 0x42, 0xb6, 0xa3, 0xc3, 0x48, 0x7e, 0x6e, + 0x6b, 0x3a, 0x28, 0x54, 0xfa, 0x85, 0xba, 0x3d, + 0xca, 0x5e, 0x9b, 0x9f, 0x0a, 0x15, 0x79, 0x2b, + 0x4e, 0xd4, 0xe5, 0xac, 0x73, 0xf3, 0xa7, 0x57, + 0x07, 0x70, 0xc0, 0xf7, 0x8c, 0x80, 0x63, 0x0d, + 0x67, 0x4a, 0xde, 0xed, 0x31, 0xc5, 0xfe, 0x18, + 0xe3, 0xa5, 0x99, 0x77, 0x26, 0xb8, 0xb4, 0x7c, + 0x11, 0x44, 0x92, 0xd9, 0x23, 0x20, 0x89, 0x2e, + 0x37, 0x3f, 0xd1, 0x5b, 0x95, 0xbc, 0xcf, 0xcd, + 0x90, 0x87, 0x97, 0xb2, 0xdc, 0xfc, 0xbe, 0x61, + 0xf2, 0x56, 0xd3, 0xab, 0x14, 0x2a, 0x5d, 0x9e, + 0x84, 0x3c, 0x39, 0x53, 0x47, 0x6d, 0x41, 0xa2, + 0x1f, 0x2d, 0x43, 0xd8, 0xb7, 0x7b, 0xa4, 0x76, + 0xc4, 0x17, 0x49, 0xec, 0x7f, 0x0c, 0x6f, 0xf6, + 0x6c, 0xa1, 0x3b, 0x52, 0x29, 0x9d, 0x55, 0xaa, + 0xfb, 0x60, 0x86, 0xb1, 0xbb, 0xcc, 0x3e, 0x5a, + 0xcb, 0x59, 0x5f, 0xb0, 0x9c, 0xa9, 0xa0, 0x51, + 0x0b, 0xf5, 0x16, 0xeb, 0x7a, 0x75, 0x2c, 0xd7, + 0x4f, 0xae, 0xd5, 0xe9, 0xe6, 0xe7, 0xad, 0xe8, + 0x74, 0xd6, 0xf4, 0xea, 0xa8, 0x50, 0x58, 0xaf +}; + +static const struct galois_field gf256 = { + .p = 255, + .log = gf256_log, + .exp = gf256_exp +}; + +/************************************************************************ + * Polynomial operations + */ + +static void poly_add(uint8_t *dst, const uint8_t *src, uint8_t c, + int shift, const struct galois_field *gf) +{ + int i; + int log_c = gf->log[c]; + + if (!c) + return; + + for (i = 0; i < MAX_POLY; i++) { + int p = i + shift; + uint8_t v = src[i]; + + if (p < 0 || p >= MAX_POLY) + continue; + if (!v) + continue; + + dst[p] ^= gf->exp[(gf->log[v] + log_c) % gf->p]; + } +} + +static uint8_t poly_eval(const uint8_t *s, uint8_t x, + const struct galois_field *gf) +{ + int i; + uint8_t sum = 0; + uint8_t log_x = gf->log[x]; + + if (!x) + return s[0]; + + for (i = 0; i < MAX_POLY; i++) { + uint8_t c = s[i]; + + if (!c) + continue; + + sum ^= gf->exp[(gf->log[c] + log_x * i) % gf->p]; + } + + return sum; +} + +/************************************************************************ + * Berlekamp-Massey algorithm for finding error locator polynomials. + */ + +static void berlekamp_massey(const uint8_t *s, int N, + const struct galois_field *gf, + uint8_t *sigma) +{ + uint8_t C[MAX_POLY]; + uint8_t B[MAX_POLY]; + int L = 0; + int m = 1; + uint8_t b = 1; + int n; + + memset(B, 0, sizeof(B)); + memset(C, 0, sizeof(C)); + B[0] = 1; + C[0] = 1; + + for (n = 0; n < N; n++) { + uint8_t d = s[n]; + uint8_t mult; + int i; + + for (i = 1; i <= L; i++) { + if (!(C[i] && s[n - i])) + continue; + + d ^= gf->exp[(gf->log[C[i]] + + gf->log[s[n - i]]) % + gf->p]; + } + + mult = gf->exp[(gf->p - gf->log[b] + gf->log[d]) % gf->p]; + + if (!d) { + m++; + } else if (L * 2 <= n) { + uint8_t T[MAX_POLY]; + + memcpy(T, C, sizeof(T)); + poly_add(C, B, mult, m, gf); + memcpy(B, T, sizeof(B)); + L = n + 1 - L; + b = d; + m = 1; + } else { + poly_add(C, B, mult, m, gf); + m++; + } + } + + memcpy(sigma, C, MAX_POLY); +} + +/************************************************************************ + * Code stream error correction + * + * Generator polynomial for GF(2^8) is x^8 + x^4 + x^3 + x^2 + 1 + */ + +static int block_syndromes(const uint8_t *data, int bs, int npar, uint8_t *s) +{ + int nonzero = 0; + int i; + + memset(s, 0, MAX_POLY); + + for (i = 0; i < npar; i++) { + int j; + + for (j = 0; j < bs; j++) { + uint8_t c = data[bs - j - 1]; + + if (!c) + continue; + + s[i] ^= gf256_exp[((int)gf256_log[c] + + i * j) % 255]; + } + + if (s[i]) + nonzero = 1; + } + + return nonzero; +} + +static void eloc_poly(uint8_t *omega, + const uint8_t *s, const uint8_t *sigma, + int npar) +{ + int i; + + memset(omega, 0, MAX_POLY); + + for (i = 0; i < npar; i++) { + const uint8_t a = sigma[i]; + const uint8_t log_a = gf256_log[a]; + int j; + + if (!a) + continue; + + for (j = 0; j + 1 < MAX_POLY; j++) { + const uint8_t b = s[j + 1]; + + if (i + j >= npar) + break; + + if (!b) + continue; + + omega[i + j] ^= + gf256_exp[(log_a + gf256_log[b]) % 255]; + } + } +} + +static quirc_decode_error_t correct_block(uint8_t *data, + const struct quirc_rs_params *ecc) +{ + int npar = ecc->bs - ecc->dw; + uint8_t s[MAX_POLY]; + uint8_t sigma[MAX_POLY]; + uint8_t sigma_deriv[MAX_POLY]; + uint8_t omega[MAX_POLY]; + int i; + + /* Compute syndrome vector */ + if (!block_syndromes(data, ecc->bs, npar, s)) + return QUIRC_SUCCESS; + + berlekamp_massey(s, npar, &gf256, sigma); + + /* Compute derivative of sigma */ + memset(sigma_deriv, 0, MAX_POLY); + for (i = 0; i + 1 < MAX_POLY; i += 2) + sigma_deriv[i] = sigma[i + 1]; + + /* Compute error evaluator polynomial */ + eloc_poly(omega, s, sigma, npar - 1); + + /* Find error locations and magnitudes */ + for (i = 0; i < ecc->bs; i++) { + uint8_t xinv = gf256_exp[255 - i]; + + if (!poly_eval(sigma, xinv, &gf256)) { + uint8_t sd_x = poly_eval(sigma_deriv, xinv, &gf256); + uint8_t omega_x = poly_eval(omega, xinv, &gf256); + uint8_t error = gf256_exp[(255 - gf256_log[sd_x] + + gf256_log[omega_x]) % 255]; + + data[ecc->bs - i - 1] ^= error; + } + } + + if (block_syndromes(data, ecc->bs, npar, s)) + return QUIRC_ERROR_DATA_ECC; + + return QUIRC_SUCCESS; +} + +/************************************************************************ + * Format value error correction + * + * Generator polynomial for GF(2^4) is x^4 + x + 1 + */ + +#define FORMAT_MAX_ERROR 3 +#define FORMAT_SYNDROMES (FORMAT_MAX_ERROR * 2) +#define FORMAT_BITS 15 + +static int format_syndromes(uint16_t u, uint8_t *s) +{ + int i; + int nonzero = 0; + + memset(s, 0, MAX_POLY); + + for (i = 0; i < FORMAT_SYNDROMES; i++) { + int j; + + s[i] = 0; + for (j = 0; j < FORMAT_BITS; j++) + if (u & (1 << j)) + s[i] ^= gf16_exp[((i + 1) * j) % 15]; + + if (s[i]) + nonzero = 1; + } + + return nonzero; +} + +static quirc_decode_error_t correct_format(uint16_t *f_ret) +{ + uint16_t u = *f_ret; + int i; + uint8_t s[MAX_POLY]; + uint8_t sigma[MAX_POLY]; + + /* Evaluate U (received codeword) at each of alpha_1 .. alpha_6 + * to get S_1 .. S_6 (but we index them from 0). + */ + if (!format_syndromes(u, s)) + return QUIRC_SUCCESS; + + berlekamp_massey(s, FORMAT_SYNDROMES, &gf16, sigma); + + /* Now, find the roots of the polynomial */ + for (i = 0; i < 15; i++) + if (!poly_eval(sigma, gf16_exp[15 - i], &gf16)) + u ^= (1 << i); + + if (format_syndromes(u, s)) + return QUIRC_ERROR_FORMAT_ECC; + + *f_ret = u; + return QUIRC_SUCCESS; +} + +/************************************************************************ + * Decoder algorithm + */ + +struct datastream { + uint8_t *raw; + int data_bits; + int ptr; + + uint8_t data[QUIRC_MAX_PAYLOAD]; +}; + +static inline int grid_bit(const struct quirc_code *code, int x, int y) +{ + int p = y * code->size + x; + return (code->cell_bitmap[p >> 3] >> (p & 7)) & 1; +} + +static quirc_decode_error_t read_format(const struct quirc_code *code, + struct quirc_data *data, int which) +{ + int i; + uint16_t format = 0; + uint16_t fdata; + quirc_decode_error_t err; + + if (which) { + for (i = 0; i < 7; i++) + format = (format << 1) | + grid_bit(code, 8, code->size - 1 - i); + for (i = 0; i < 8; i++) + format = (format << 1) | + grid_bit(code, code->size - 8 + i, 8); + } else { + static const int xs[15] = { + 8, 8, 8, 8, 8, 8, 8, 8, 7, 5, 4, 3, 2, 1, 0 + }; + static const int ys[15] = { + 0, 1, 2, 3, 4, 5, 7, 8, 8, 8, 8, 8, 8, 8, 8 + }; + + for (i = 14; i >= 0; i--) + format = (format << 1) | grid_bit(code, xs[i], ys[i]); + } + + format ^= 0x5412; + + err = correct_format(&format); + if (err) + return err; + + fdata = format >> 10; + data->ecc_level = fdata >> 3; + data->mask = fdata & 7; + + return QUIRC_SUCCESS; +} + +static int mask_bit(int mask, int i, int j) +{ + switch (mask) { + case 0: return !((i + j) % 2); + case 1: return !(i % 2); + case 2: return !(j % 3); + case 3: return !((i + j) % 3); + case 4: return !(((i / 2) + (j / 3)) % 2); + case 5: return !((i * j) % 2 + (i * j) % 3); + case 6: return !(((i * j) % 2 + (i * j) % 3) % 2); + case 7: return !(((i * j) % 3 + (i + j) % 2) % 2); + } + + return 0; +} + +static int reserved_cell(int version, int i, int j) +{ + const struct quirc_version_info *ver = &quirc_version_db[version]; + int size = version * 4 + 17; + int ai = -1, aj = -1, a; + + /* Finder + format: top left */ + if (i < 9 && j < 9) + return 1; + + /* Finder + format: bottom left */ + if (i + 8 >= size && j < 9) + return 1; + + /* Finder + format: top right */ + if (i < 9 && j + 8 >= size) + return 1; + + /* Exclude timing patterns */ + if (i == 6 || j == 6) + return 1; + + /* Exclude version info, if it exists. Version info sits adjacent to + * the top-right and bottom-left finders in three rows, bounded by + * the timing pattern. + */ + if (version >= 7) { + if (i < 6 && j + 11 >= size) + return 1; + if (i + 11 >= size && j < 6) + return 1; + } + + /* Exclude alignment patterns */ + for (a = 0; a < QUIRC_MAX_ALIGNMENT && ver->apat[a]; a++) { + int p = ver->apat[a]; + + if (abs(p - i) < 3) + ai = a; + if (abs(p - j) < 3) + aj = a; + } + + if (ai >= 0 && aj >= 0) { + a--; + if (ai > 0 && ai < a) + return 1; + if (aj > 0 && aj < a) + return 1; + if (aj == a && ai == a) + return 1; + } + + return 0; +} + +static void read_bit(const struct quirc_code *code, + struct quirc_data *data, + struct datastream *ds, int i, int j) +{ + int bitpos = ds->data_bits & 7; + int bytepos = ds->data_bits >> 3; + int v = grid_bit(code, j, i); + + if (mask_bit(data->mask, i, j)) + v ^= 1; + + if (v) + ds->raw[bytepos] |= (0x80 >> bitpos); + + ds->data_bits++; +} + +static void read_data(const struct quirc_code *code, + struct quirc_data *data, + struct datastream *ds) +{ + int y = code->size - 1; + int x = code->size - 1; + int dir = -1; + + while (x > 0) { + if (x == 6) + x--; + + if (!reserved_cell(data->version, y, x)) + read_bit(code, data, ds, y, x); + + if (!reserved_cell(data->version, y, x - 1)) + read_bit(code, data, ds, y, x - 1); + + y += dir; + if (y < 0 || y >= code->size) { + dir = -dir; + x -= 2; + y += dir; + } + } +} + +static quirc_decode_error_t codestream_ecc(struct quirc_data *data, + struct datastream *ds) +{ + const struct quirc_version_info *ver = + &quirc_version_db[data->version]; + const struct quirc_rs_params *sb_ecc = &ver->ecc[data->ecc_level]; + struct quirc_rs_params lb_ecc; + const int lb_count = + (ver->data_bytes - sb_ecc->bs * sb_ecc->ns) / (sb_ecc->bs + 1); + const int bc = lb_count + sb_ecc->ns; + const int ecc_offset = sb_ecc->dw * bc + lb_count; + int dst_offset = 0; + int i; + + memcpy(&lb_ecc, sb_ecc, sizeof(lb_ecc)); + lb_ecc.dw++; + lb_ecc.bs++; + + for (i = 0; i < bc; i++) { + uint8_t *dst = ds->data + dst_offset; + const struct quirc_rs_params *ecc = + (i < sb_ecc->ns) ? sb_ecc : &lb_ecc; + const int num_ec = ecc->bs - ecc->dw; + quirc_decode_error_t err; + int j; + + for (j = 0; j < ecc->dw; j++) + dst[j] = ds->raw[j * bc + i]; + for (j = 0; j < num_ec; j++) + dst[ecc->dw + j] = ds->raw[ecc_offset + j * bc + i]; + + err = correct_block(dst, ecc); + if (err) + return err; + + dst_offset += ecc->dw; + } + + ds->data_bits = dst_offset * 8; + + return QUIRC_SUCCESS; +} + +static inline int bits_remaining(const struct datastream *ds) +{ + return ds->data_bits - ds->ptr; +} + +static int take_bits(struct datastream *ds, int len) +{ + int ret = 0; + + while (len && (ds->ptr < ds->data_bits)) { + uint8_t b = ds->data[ds->ptr >> 3]; + int bitpos = ds->ptr & 7; + + ret <<= 1; + if ((b << bitpos) & 0x80) + ret |= 1; + + ds->ptr++; + len--; + } + + return ret; +} + +static int numeric_tuple(struct quirc_data *data, + struct datastream *ds, + int bits, int digits) +{ + int tuple; + int i; + + if (bits_remaining(ds) < bits) + return -1; + + tuple = take_bits(ds, bits); + + for (i = digits - 1; i >= 0; i--) { + data->payload[data->payload_len + i] = tuple % 10 + '0'; + tuple /= 10; + } + + data->payload_len += digits; + return 0; +} + +static quirc_decode_error_t decode_numeric(struct quirc_data *data, + struct datastream *ds) +{ + int bits = 14; + int count; + + if (data->version < 10) + bits = 10; + else if (data->version < 27) + bits = 12; + + count = take_bits(ds, bits); + if (data->payload_len + count + 1 > QUIRC_MAX_PAYLOAD) + return QUIRC_ERROR_DATA_OVERFLOW; + + while (count >= 3) { + if (numeric_tuple(data, ds, 10, 3) < 0) + return QUIRC_ERROR_DATA_UNDERFLOW; + count -= 3; + } + + if (count >= 2) { + if (numeric_tuple(data, ds, 7, 2) < 0) + return QUIRC_ERROR_DATA_UNDERFLOW; + count -= 2; + } + + if (count) { + if (numeric_tuple(data, ds, 4, 1) < 0) + return QUIRC_ERROR_DATA_UNDERFLOW; + count--; + } + + return QUIRC_SUCCESS; +} + +static int alpha_tuple(struct quirc_data *data, + struct datastream *ds, + int bits, int digits) +{ + int tuple; + int i; + + if (bits_remaining(ds) < bits) + return -1; + + tuple = take_bits(ds, bits); + + for (i = 0; i < digits; i++) { + static const char *alpha_map = + "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:"; + + data->payload[data->payload_len + digits - i - 1] = + alpha_map[tuple % 45]; + tuple /= 45; + } + + data->payload_len += digits; + return 0; +} + +static quirc_decode_error_t decode_alpha(struct quirc_data *data, + struct datastream *ds) +{ + int bits = 13; + int count; + + if (data->version < 10) + bits = 9; + else if (data->version < 27) + bits = 11; + + count = take_bits(ds, bits); + if (data->payload_len + count + 1 > QUIRC_MAX_PAYLOAD) + return QUIRC_ERROR_DATA_OVERFLOW; + + while (count >= 2) { + if (alpha_tuple(data, ds, 11, 2) < 0) + return QUIRC_ERROR_DATA_UNDERFLOW; + count -= 2; + } + + if (count) { + if (alpha_tuple(data, ds, 6, 1) < 0) + return QUIRC_ERROR_DATA_UNDERFLOW; + count--; + } + + return QUIRC_SUCCESS; +} + +static quirc_decode_error_t decode_byte(struct quirc_data *data, + struct datastream *ds) +{ + int bits = 16; + int count; + int i; + + if (data->version < 10) + bits = 8; + + count = take_bits(ds, bits); + if (data->payload_len + count + 1 > QUIRC_MAX_PAYLOAD) + return QUIRC_ERROR_DATA_OVERFLOW; + if (bits_remaining(ds) < count * 8) + return QUIRC_ERROR_DATA_UNDERFLOW; + + for (i = 0; i < count; i++) + data->payload[data->payload_len++] = take_bits(ds, 8); + + return QUIRC_SUCCESS; +} + +static quirc_decode_error_t decode_kanji(struct quirc_data *data, + struct datastream *ds) +{ + int bits = 12; + int count; + int i; + + if (data->version < 10) + bits = 8; + else if (data->version < 27) + bits = 10; + + count = take_bits(ds, bits); + if (data->payload_len + count * 2 + 1 > QUIRC_MAX_PAYLOAD) + return QUIRC_ERROR_DATA_OVERFLOW; + if (bits_remaining(ds) < count * 13) + return QUIRC_ERROR_DATA_UNDERFLOW; + + for (i = 0; i < count; i++) { + int d = take_bits(ds, 13); + int msB = d / 0xc0; + int lsB = d % 0xc0; + int intermediate = (msB << 8) | lsB; + uint16_t sjw; + + if (intermediate + 0x8140 <= 0x9ffc) { + /* bytes are in the range 0x8140 to 0x9FFC */ + sjw = intermediate + 0x8140; + } else { + /* bytes are in the range 0xE040 to 0xEBBF */ + sjw = intermediate + 0xc140; + } + + data->payload[data->payload_len++] = sjw >> 8; + data->payload[data->payload_len++] = sjw & 0xff; + } + + return QUIRC_SUCCESS; +} + +static quirc_decode_error_t decode_eci(struct quirc_data *data, + struct datastream *ds) +{ + if (bits_remaining(ds) < 8) + return QUIRC_ERROR_DATA_UNDERFLOW; + + data->eci = take_bits(ds, 8); + + if ((data->eci & 0xc0) == 0x80) { + if (bits_remaining(ds) < 8) + return QUIRC_ERROR_DATA_UNDERFLOW; + + data->eci = (data->eci << 8) | take_bits(ds, 8); + } else if ((data->eci & 0xe0) == 0xc0) { + if (bits_remaining(ds) < 16) + return QUIRC_ERROR_DATA_UNDERFLOW; + + data->eci = (data->eci << 16) | take_bits(ds, 16); + } + + return QUIRC_SUCCESS; +} + +static quirc_decode_error_t decode_payload(struct quirc_data *data, + struct datastream *ds) +{ + while (bits_remaining(ds) >= 4) { + quirc_decode_error_t err = QUIRC_SUCCESS; + int type = take_bits(ds, 4); + + switch (type) { + case QUIRC_DATA_TYPE_NUMERIC: + err = decode_numeric(data, ds); + break; + + case QUIRC_DATA_TYPE_ALPHA: + err = decode_alpha(data, ds); + break; + + case QUIRC_DATA_TYPE_BYTE: + err = decode_byte(data, ds); + break; + + case QUIRC_DATA_TYPE_KANJI: + err = decode_kanji(data, ds); + break; + + case 7: + err = decode_eci(data, ds); + break; + + default: + goto done; + } + + if (err) + return err; + + if (!(type & (type - 1)) && (type > data->data_type)) + data->data_type = type; + } +done: + + /* Add nul terminator to all payloads */ + if (data->payload_len >= (int) sizeof(data->payload)) + data->payload_len--; + data->payload[data->payload_len] = 0; + + return QUIRC_SUCCESS; +} + +quirc_decode_error_t quirc_decode(const struct quirc_code *code, + struct quirc_data *data) +{ + quirc_decode_error_t err; +#if QUIRC_SMALL_STACK + struct datastream *dsp = QUIRC_CALLOC(sizeof(*dsp), 1); +#define ds (*dsp) +#else + struct datastream ds = {0}; +#endif + + if ((code->size - 17) % 4) { +#if QUIRC_SMALL_STACK + QUIRC_FREE(dsp); +#endif + return QUIRC_ERROR_INVALID_GRID_SIZE; + } + + memset(data, 0, sizeof(*data)); + + data->version = (code->size - 17) / 4; + + if (data->version < 1 || + data->version > QUIRC_MAX_VERSION) { +#if QUIRC_SMALL_STACK + QUIRC_FREE(dsp); +#endif + return QUIRC_ERROR_INVALID_VERSION; + } + + /* Read format information -- try both locations */ + err = read_format(code, data, 0); + if (err) + err = read_format(code, data, 1); + if (err) { +#if QUIRC_SMALL_STACK + QUIRC_FREE(dsp); +#endif + return err; + } + + /* + * Borrow data->payload to store the raw bits. + * It's only used during read_data + coddestream_ecc below. + * + * This trick saves the size of struct datastream, which we allocate + * on the stack. + */ + + ds.raw = data->payload; + + read_data(code, data, &ds); + err = codestream_ecc(data, &ds); + if (err) + return err; + + ds.raw = NULL; /* We've done with this buffer. */ + + err = decode_payload(data, &ds); +#if QUIRC_SMALL_STACK + QUIRC_FREE(dsp); +#undef ds +#endif + + if (err) + return err; + + return QUIRC_SUCCESS; +} + +void quirc_flip(struct quirc_code *code) +{ +#if QUIRC_SMALL_STACK + static struct quirc_code *flipped_p = NULL; + if(!flipped_p) { + flipped_p = QUIRC_CALLOC(sizeof(*flipped_p), 1); + } +#define flipped (*flipped_p) +#else + struct quirc_code flipped = {0}; +#endif + unsigned int offset = 0; + for (int y = 0; y < code->size; y++) { + for (int x = 0; x < code->size; x++) { + if (grid_bit(code, y, x)) { + flipped.cell_bitmap[offset >> 3u] |= (1u << (offset & 7u)); + } + offset++; + } + } + memcpy(&code->cell_bitmap, &flipped.cell_bitmap, sizeof(flipped.cell_bitmap)); +#if QUIRC_SMALL_STACK + QUIRC_FREE(flipped_p); +#undef flipped +#endif +} diff --git a/circuitpython/lib/quirc/lib/identify.c b/circuitpython/lib/quirc/lib/identify.c new file mode 100644 index 0000000..6dc4ac5 --- /dev/null +++ b/circuitpython/lib/quirc/lib/identify.c @@ -0,0 +1,1140 @@ +/* quirc - QR-code recognition library + * Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <limits.h> +#include <string.h> +#include <stdbool.h> +#include <stdlib.h> +#include <math.h> +#include "quirc_internal.h" + +/************************************************************************ + * Linear algebra routines + */ + +static int line_intersect(const struct quirc_point *p0, + const struct quirc_point *p1, + const struct quirc_point *q0, + const struct quirc_point *q1, + struct quirc_point *r) +{ + /* (a, b) is perpendicular to line p */ + int a = -(p1->y - p0->y); + int b = p1->x - p0->x; + + /* (c, d) is perpendicular to line q */ + int c = -(q1->y - q0->y); + int d = q1->x - q0->x; + + /* e and f are dot products of the respective vectors with p and q */ + int e = a * p1->x + b * p1->y; + int f = c * q1->x + d * q1->y; + + /* Now we need to solve: + * [a b] [rx] [e] + * [c d] [ry] = [f] + * + * We do this by inverting the matrix and applying it to (e, f): + * [ d -b] [e] [rx] + * 1/det [-c a] [f] = [ry] + */ + int det = (a * d) - (b * c); + + if (!det) + return 0; + + r->x = (d * e - b * f) / det; + r->y = (-c * e + a * f) / det; + + return 1; +} + +static void perspective_setup(float *c, + const struct quirc_point *rect, + float w, float h) +{ + float x0 = rect[0].x; + float y0 = rect[0].y; + float x1 = rect[1].x; + float y1 = rect[1].y; + float x2 = rect[2].x; + float y2 = rect[2].y; + float x3 = rect[3].x; + float y3 = rect[3].y; + + float wden = w * (x2*y3 - x3*y2 + (x3-x2)*y1 + x1*(y2-y3)); + float hden = h * (x2*y3 + x1*(y2-y3) - x3*y2 + (x3-x2)*y1); + + c[0] = (x1*(x2*y3-x3*y2) + x0*(-x2*y3+x3*y2+(x2-x3)*y1) + + x1*(x3-x2)*y0) / wden; + c[1] = -(x0*(x2*y3+x1*(y2-y3)-x2*y1) - x1*x3*y2 + x2*x3*y1 + + (x1*x3-x2*x3)*y0) / hden; + c[2] = x0; + c[3] = (y0*(x1*(y3-y2)-x2*y3+x3*y2) + y1*(x2*y3-x3*y2) + + x0*y1*(y2-y3)) / wden; + c[4] = (x0*(y1*y3-y2*y3) + x1*y2*y3 - x2*y1*y3 + + y0*(x3*y2-x1*y2+(x2-x3)*y1)) / hden; + c[5] = y0; + c[6] = (x1*(y3-y2) + x0*(y2-y3) + (x2-x3)*y1 + (x3-x2)*y0) / wden; + c[7] = (-x2*y3 + x1*y3 + x3*y2 + x0*(y1-y2) - x3*y1 + (x2-x1)*y0) / + hden; +} + +static void perspective_map(const float *c, + float u, float v, struct quirc_point *ret) +{ + float den = c[6]*u + c[7]*v + 1.0f; + float x = (c[0]*u + c[1]*v + c[2]) / den; + float y = (c[3]*u + c[4]*v + c[5]) / den; + + ret->x = (int) nearbyintf(x); + ret->y = (int) nearbyintf(y); +} + +static void perspective_unmap(const float *c, + const struct quirc_point *in, + float *u, float *v) +{ + float x = in->x; + float y = in->y; + float den = -c[0]*c[7]*y + c[1]*c[6]*y + (c[3]*c[7]-c[4]*c[6])*x + + c[0]*c[4] - c[1]*c[3]; + + *u = -(c[1]*(y-c[5]) - c[2]*c[7]*y + (c[5]*c[7]-c[4])*x + c[2]*c[4]) / + den; + *v = (c[0]*(y-c[5]) - c[2]*c[6]*y + (c[5]*c[6]-c[3])*x + c[2]*c[3]) / + den; +} + +/************************************************************************ + * Span-based floodfill routine + */ + +typedef void (*span_func_t)(void *user_data, int y, int left, int right); + +static void flood_fill_line(struct quirc *q, int x, int y, + int from, int to, + span_func_t func, void *user_data, + int *leftp, int *rightp) +{ + quirc_pixel_t *row; + int left; + int right; + int i; + + row = q->pixels + y * q->w; + QUIRC_ASSERT(row[x] == from); + + left = x; + right = x; + + while (left > 0 && row[left - 1] == from) + left--; + + while (right < q->w - 1 && row[right + 1] == from) + right++; + + /* Fill the extent */ + for (i = left; i <= right; i++) + row[i] = to; + + /* Return the processed range */ + *leftp = left; + *rightp = right; + + if (func) + func(user_data, y, left, right); +} + +static struct quirc_flood_fill_vars *flood_fill_call_next( + struct quirc *q, + quirc_pixel_t *row, + int from, int to, + span_func_t func, void *user_data, + struct quirc_flood_fill_vars *vars, + int direction) +{ + int *leftp; + + if (direction < 0) { + leftp = &vars->left_up; + } else { + leftp = &vars->left_down; + } + + while (*leftp <= vars->right) { + if (row[*leftp] == from) { + struct quirc_flood_fill_vars *next_vars; + int next_left; + + /* Set up the next context */ + next_vars = vars + 1; + next_vars->y = vars->y + direction; + + /* Fill the extent */ + flood_fill_line(q, + *leftp, + next_vars->y, + from, to, + func, user_data, + &next_left, + &next_vars->right); + next_vars->left_down = next_left; + next_vars->left_up = next_left; + + return next_vars; + } + (*leftp)++; + } + return NULL; +} + +static void flood_fill_seed(struct quirc *q, + int x0, int y0, + int from, int to, + span_func_t func, void *user_data) +{ + struct quirc_flood_fill_vars *const stack = q->flood_fill_vars; + const size_t stack_size = q->num_flood_fill_vars; + const struct quirc_flood_fill_vars *const last_vars = + &stack[stack_size - 1]; + + QUIRC_ASSERT(from != to); + QUIRC_ASSERT(q->pixels[y0 * q->w + x0] == from); + + struct quirc_flood_fill_vars *next_vars; + int next_left; + + /* Set up the first context */ + next_vars = stack; + next_vars->y = y0; + + /* Fill the extent */ + flood_fill_line(q, x0, next_vars->y, from, to, + func, user_data, + &next_left, &next_vars->right); + next_vars->left_down = next_left; + next_vars->left_up = next_left; + + while (true) { + struct quirc_flood_fill_vars * const vars = next_vars; + quirc_pixel_t *row; + + if (vars == last_vars) { + /* + * "Stack overflow". + * Just stop and return. + * This can be caused by very complex shapes in + * the image, which is not likely a part of + * a valid QR code anyway. + */ + break; + } + + /* Seed new flood-fills */ + if (vars->y > 0) { + row = q->pixels + (vars->y - 1) * q->w; + + next_vars = flood_fill_call_next(q, row, + from, to, + func, user_data, + vars, -1); + if (next_vars != NULL) { + continue; + } + } + + if (vars->y < q->h - 1) { + row = q->pixels + (vars->y + 1) * q->w; + + next_vars = flood_fill_call_next(q, row, + from, to, + func, user_data, + vars, 1); + if (next_vars != NULL) { + continue; + } + } + + if (vars > stack) { + /* Restore the previous context */ + next_vars = vars - 1; + continue; + } + + /* We've done. */ + break; + } +} + +/************************************************************************ + * Adaptive thresholding + */ + +static uint8_t otsu(const struct quirc *q) +{ + unsigned int numPixels = q->w * q->h; + + // Calculate histogram + unsigned int histogram[UINT8_MAX + 1]; + (void)memset(histogram, 0, sizeof(histogram)); + uint8_t* ptr = q->image; + unsigned int length = numPixels; + while (length--) { + uint8_t value = *ptr++; + histogram[value]++; + } + + // Calculate weighted sum of histogram values + float sum = 0; + unsigned int i = 0; + for (i = 0; i <= UINT8_MAX; ++i) { + sum += i * histogram[i]; + } + + // Compute threshold + float sumB = 0; + unsigned int q1 = 0; + float max = 0; + uint8_t threshold = 0; + for (i = 0; i <= UINT8_MAX; ++i) { + // Weighted background + q1 += histogram[i]; + if (q1 == 0) + continue; + + // Weighted foreground + const unsigned int q2 = numPixels - q1; + if (q2 == 0) + break; + + sumB += i * histogram[i]; + const float m1 = sumB / q1; + const float m2 = (sum - sumB) / q2; + const float m1m2 = m1 - m2; + const float variance = m1m2 * m1m2 * q1 * q2; + if (variance >= max) { + threshold = i; + max = variance; + } + } + + return threshold; +} + +static void area_count(void *user_data, int y, int left, int right) +{ + ((struct quirc_region *)user_data)->count += right - left + 1; +} + +static int region_code(struct quirc *q, int x, int y) +{ + int pixel; + struct quirc_region *box; + int region; + + if (x < 0 || y < 0 || x >= q->w || y >= q->h) + return -1; + + pixel = q->pixels[y * q->w + x]; + + if (pixel >= QUIRC_PIXEL_REGION) + return pixel; + + if (pixel == QUIRC_PIXEL_WHITE) + return -1; + + if (q->num_regions >= QUIRC_MAX_REGIONS) + return -1; + + region = q->num_regions; + box = &q->regions[q->num_regions++]; + + memset(box, 0, sizeof(*box)); + + box->seed.x = x; + box->seed.y = y; + box->capstone = -1; + + flood_fill_seed(q, x, y, pixel, region, area_count, box); + + return region; +} + +struct polygon_score_data { + struct quirc_point ref; + + int scores[4]; + struct quirc_point *corners; +}; + +static void find_one_corner(void *user_data, int y, int left, int right) +{ + struct polygon_score_data *psd = + (struct polygon_score_data *)user_data; + int xs[2] = {left, right}; + int dy = y - psd->ref.y; + int i; + + for (i = 0; i < 2; i++) { + int dx = xs[i] - psd->ref.x; + int d = dx * dx + dy * dy; + + if (d > psd->scores[0]) { + psd->scores[0] = d; + psd->corners[0].x = xs[i]; + psd->corners[0].y = y; + } + } +} + +static void find_other_corners(void *user_data, int y, int left, int right) +{ + struct polygon_score_data *psd = + (struct polygon_score_data *)user_data; + int xs[2] = {left, right}; + int i; + + for (i = 0; i < 2; i++) { + int up = xs[i] * psd->ref.x + y * psd->ref.y; + int right = xs[i] * -psd->ref.y + y * psd->ref.x; + int scores[4] = {up, right, -up, -right}; + int j; + + for (j = 0; j < 4; j++) { + if (scores[j] > psd->scores[j]) { + psd->scores[j] = scores[j]; + psd->corners[j].x = xs[i]; + psd->corners[j].y = y; + } + } + } +} + +static void find_region_corners(struct quirc *q, + int rcode, const struct quirc_point *ref, + struct quirc_point *corners) +{ + struct quirc_region *region = &q->regions[rcode]; + struct polygon_score_data psd; + int i; + + memset(&psd, 0, sizeof(psd)); + psd.corners = corners; + + memcpy(&psd.ref, ref, sizeof(psd.ref)); + psd.scores[0] = -1; + flood_fill_seed(q, region->seed.x, region->seed.y, + rcode, QUIRC_PIXEL_BLACK, + find_one_corner, &psd); + + psd.ref.x = psd.corners[0].x - psd.ref.x; + psd.ref.y = psd.corners[0].y - psd.ref.y; + + for (i = 0; i < 4; i++) + memcpy(&psd.corners[i], ®ion->seed, + sizeof(psd.corners[i])); + + i = region->seed.x * psd.ref.x + region->seed.y * psd.ref.y; + psd.scores[0] = i; + psd.scores[2] = -i; + i = region->seed.x * -psd.ref.y + region->seed.y * psd.ref.x; + psd.scores[1] = i; + psd.scores[3] = -i; + + flood_fill_seed(q, region->seed.x, region->seed.y, + QUIRC_PIXEL_BLACK, rcode, + find_other_corners, &psd); +} + +static void record_capstone(struct quirc *q, int ring, int stone) +{ + struct quirc_region *stone_reg = &q->regions[stone]; + struct quirc_region *ring_reg = &q->regions[ring]; + struct quirc_capstone *capstone; + int cs_index; + + if (q->num_capstones >= QUIRC_MAX_CAPSTONES) + return; + + cs_index = q->num_capstones; + capstone = &q->capstones[q->num_capstones++]; + + memset(capstone, 0, sizeof(*capstone)); + + capstone->qr_grid = -1; + capstone->ring = ring; + capstone->stone = stone; + stone_reg->capstone = cs_index; + ring_reg->capstone = cs_index; + + /* Find the corners of the ring */ + find_region_corners(q, ring, &stone_reg->seed, capstone->corners); + + /* Set up the perspective transform and find the center */ + perspective_setup(capstone->c, capstone->corners, 7.0, 7.0); + perspective_map(capstone->c, 3.5, 3.5, &capstone->center); +} + +static void test_capstone(struct quirc *q, unsigned int x, unsigned int y, + unsigned int *pb) +{ + int ring_right = region_code(q, x - pb[4], y); + int stone = region_code(q, x - pb[4] - pb[3] - pb[2], y); + int ring_left = region_code(q, x - pb[4] - pb[3] - + pb[2] - pb[1] - pb[0], + y); + struct quirc_region *stone_reg; + struct quirc_region *ring_reg; + unsigned int ratio; + + if (ring_left < 0 || ring_right < 0 || stone < 0) + return; + + /* Left and ring of ring should be connected */ + if (ring_left != ring_right) + return; + + /* Ring should be disconnected from stone */ + if (ring_left == stone) + return; + + stone_reg = &q->regions[stone]; + ring_reg = &q->regions[ring_left]; + + /* Already detected */ + if (stone_reg->capstone >= 0 || ring_reg->capstone >= 0) + return; + + /* Ratio should ideally be 37.5 */ + ratio = stone_reg->count * 100 / ring_reg->count; + if (ratio < 10 || ratio > 70) + return; + + record_capstone(q, ring_left, stone); +} + +static void finder_scan(struct quirc *q, unsigned int y) +{ + quirc_pixel_t *row = q->pixels + y * q->w; + unsigned int x; + unsigned int w = (unsigned)q->w; + int last_color = 0; + unsigned int run_length = 0; + unsigned int run_count = 0; + unsigned int pb[5]; + + memset(pb, 0, sizeof(pb)); + for (x = 0; x < w; x++) { + int color = row[x] ? 1 : 0; + + if (x && color != last_color) { + memmove(pb, pb + 1, sizeof(pb[0]) * 4); + pb[4] = run_length; + run_length = 0; + run_count++; + + if (!color && run_count >= 5) { + const int scale = 16; + static const unsigned int check[5] = {1, 1, 3, 1, 1}; + unsigned int avg, err; + unsigned int i; + int ok = 1; + + avg = (pb[0] + pb[1] + pb[3] + pb[4]) * scale / 4; + err = avg * 3 / 4; + + for (i = 0; i < 5; i++) + if (pb[i] * scale < check[i] * avg - err || + pb[i] * scale > check[i] * avg + err) + ok = 0; + + if (ok) + test_capstone(q, x, y, pb); + } + } + + run_length++; + last_color = color; + } +} + +static void find_alignment_pattern(struct quirc *q, int index) +{ + struct quirc_grid *qr = &q->grids[index]; + struct quirc_capstone *c0 = &q->capstones[qr->caps[0]]; + struct quirc_capstone *c2 = &q->capstones[qr->caps[2]]; + struct quirc_point a; + struct quirc_point b; + struct quirc_point c; + int size_estimate; + int step_size = 1; + int dir = 0; + float u, v; + + /* Grab our previous estimate of the alignment pattern corner */ + memcpy(&b, &qr->align, sizeof(b)); + + /* Guess another two corners of the alignment pattern so that we + * can estimate its size. + */ + perspective_unmap(c0->c, &b, &u, &v); + perspective_map(c0->c, u, v + 1.0f, &a); + perspective_unmap(c2->c, &b, &u, &v); + perspective_map(c2->c, u + 1.0f, v, &c); + + size_estimate = abs((a.x - b.x) * -(c.y - b.y) + + (a.y - b.y) * (c.x - b.x)); + + /* Spiral outwards from the estimate point until we find something + * roughly the right size. Don't look too far from the estimate + * point. + */ + while (step_size * step_size < size_estimate * 100) { + static const int dx_map[] = {1, 0, -1, 0}; + static const int dy_map[] = {0, -1, 0, 1}; + int i; + + for (i = 0; i < step_size; i++) { + int code = region_code(q, b.x, b.y); + + if (code >= 0) { + struct quirc_region *reg = &q->regions[code]; + + if (reg->count >= size_estimate / 2 && + reg->count <= size_estimate * 2) { + qr->align_region = code; + return; + } + } + + b.x += dx_map[dir]; + b.y += dy_map[dir]; + } + + dir = (dir + 1) % 4; + if (!(dir & 1)) + step_size++; + } +} + +static void find_leftmost_to_line(void *user_data, int y, int left, int right) +{ + struct polygon_score_data *psd = + (struct polygon_score_data *)user_data; + int xs[2] = {left, right}; + int i; + + for (i = 0; i < 2; i++) { + int d = -psd->ref.y * xs[i] + psd->ref.x * y; + + if (d < psd->scores[0]) { + psd->scores[0] = d; + psd->corners[0].x = xs[i]; + psd->corners[0].y = y; + } + } +} + +static float distance(struct quirc_point a, struct quirc_point b) +{ + return sqrtf((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y)); +} +/* Estimate grid size by determing distance between capstones + */ +static void measure_grid_size(struct quirc *q, int index) +{ + struct quirc_grid *qr = &q->grids[index]; + + struct quirc_capstone *a = &(q->capstones[qr->caps[0]]); + struct quirc_capstone *b = &(q->capstones[qr->caps[1]]); + struct quirc_capstone *c = &(q->capstones[qr->caps[2]]); + + float ab = distance(b->corners[0], a->corners[3]); + float capstone_ab_size = (distance(b->corners[0], b->corners[3]) + distance(a->corners[0], a->corners[3]))/2.0f; + float ver_grid = 7.0f * ab / capstone_ab_size; + + float bc = distance(b->corners[0], c->corners[1]); + float capstone_bc_size = (distance(b->corners[0], b->corners[1]) + distance(c->corners[0], c->corners[1]))/2.0f; + float hor_grid = 7.0f * bc / capstone_bc_size; + + float grid_size_estimate = (ver_grid + hor_grid) / 2; + + qr->grid_size = 4*((int)(grid_size_estimate - 17.0f + 2.0f) / 4) + 17; +} + +/* Read a cell from a grid using the currently set perspective + * transform. Returns +/- 1 for black/white, 0 for cells which are + * out of image bounds. + */ +static int read_cell(const struct quirc *q, int index, int x, int y) +{ + const struct quirc_grid *qr = &q->grids[index]; + struct quirc_point p; + + perspective_map(qr->c, x + 0.5f, y + 0.5f, &p); + if (p.y < 0 || p.y >= q->h || p.x < 0 || p.x >= q->w) + return 0; + + return q->pixels[p.y * q->w + p.x] ? 1 : -1; +} + +static int fitness_cell(const struct quirc *q, int index, int x, int y) +{ + const struct quirc_grid *qr = &q->grids[index]; + int score = 0; + int u, v; + + for (v = 0; v < 3; v++) + for (u = 0; u < 3; u++) { + static const float offsets[] = {0.3f, 0.5f, 0.7f}; + struct quirc_point p; + + perspective_map(qr->c, x + offsets[u], + y + offsets[v], &p); + if (p.y < 0 || p.y >= q->h || p.x < 0 || p.x >= q->w) + continue; + + if (q->pixels[p.y * q->w + p.x]) + score++; + else + score--; + } + + return score; +} + +static int fitness_ring(const struct quirc *q, int index, int cx, int cy, + int radius) +{ + int i; + int score = 0; + + for (i = 0; i < radius * 2; i++) { + score += fitness_cell(q, index, cx - radius + i, cy - radius); + score += fitness_cell(q, index, cx - radius, cy + radius - i); + score += fitness_cell(q, index, cx + radius, cy - radius + i); + score += fitness_cell(q, index, cx + radius - i, cy + radius); + } + + return score; +} + +static int fitness_apat(const struct quirc *q, int index, int cx, int cy) +{ + return fitness_cell(q, index, cx, cy) - + fitness_ring(q, index, cx, cy, 1) + + fitness_ring(q, index, cx, cy, 2); +} + +static int fitness_capstone(const struct quirc *q, int index, int x, int y) +{ + x += 3; + y += 3; + + return fitness_cell(q, index, x, y) + + fitness_ring(q, index, x, y, 1) - + fitness_ring(q, index, x, y, 2) + + fitness_ring(q, index, x, y, 3); +} + +/* Compute a fitness score for the currently configured perspective + * transform, using the features we expect to find by scanning the + * grid. + */ +static int fitness_all(const struct quirc *q, int index) +{ + const struct quirc_grid *qr = &q->grids[index]; + int version = (qr->grid_size - 17) / 4; + const struct quirc_version_info *info = &quirc_version_db[version]; + int score = 0; + int i, j; + int ap_count; + + /* Check the timing pattern */ + for (i = 0; i < qr->grid_size - 14; i++) { + int expect = (i & 1) ? 1 : -1; + + score += fitness_cell(q, index, i + 7, 6) * expect; + score += fitness_cell(q, index, 6, i + 7) * expect; + } + + /* Check capstones */ + score += fitness_capstone(q, index, 0, 0); + score += fitness_capstone(q, index, qr->grid_size - 7, 0); + score += fitness_capstone(q, index, 0, qr->grid_size - 7); + + if (version < 0 || version > QUIRC_MAX_VERSION) + return score; + + /* Check alignment patterns */ + ap_count = 0; + while ((ap_count < QUIRC_MAX_ALIGNMENT) && info->apat[ap_count]) + ap_count++; + + for (i = 1; i + 1 < ap_count; i++) { + score += fitness_apat(q, index, 6, info->apat[i]); + score += fitness_apat(q, index, info->apat[i], 6); + } + + for (i = 1; i < ap_count; i++) + for (j = 1; j < ap_count; j++) + score += fitness_apat(q, index, + info->apat[i], info->apat[j]); + + return score; +} + +static void jiggle_perspective(struct quirc *q, int index) +{ + struct quirc_grid *qr = &q->grids[index]; + int best = fitness_all(q, index); + int pass; + float adjustments[8]; + int i; + + for (i = 0; i < 8; i++) + adjustments[i] = qr->c[i] * 0.02f; + + for (pass = 0; pass < 5; pass++) { + for (i = 0; i < 16; i++) { + int j = i >> 1; + int test; + float old = qr->c[j]; + float step = adjustments[j]; + float new; + + if (i & 1) + new = old + step; + else + new = old - step; + + qr->c[j] = new; + test = fitness_all(q, index); + + if (test > best) + best = test; + else + qr->c[j] = old; + } + + for (i = 0; i < 8; i++) + adjustments[i] *= 0.5f; + } +} + +/* Once the capstones are in place and an alignment point has been + * chosen, we call this function to set up a grid-reading perspective + * transform. + */ +static void setup_qr_perspective(struct quirc *q, int index) +{ + struct quirc_grid *qr = &q->grids[index]; + struct quirc_point rect[4]; + + /* Set up the perspective map for reading the grid */ + memcpy(&rect[0], &q->capstones[qr->caps[1]].corners[0], + sizeof(rect[0])); + memcpy(&rect[1], &q->capstones[qr->caps[2]].corners[0], + sizeof(rect[0])); + memcpy(&rect[2], &qr->align, sizeof(rect[0])); + memcpy(&rect[3], &q->capstones[qr->caps[0]].corners[0], + sizeof(rect[0])); + perspective_setup(qr->c, rect, qr->grid_size - 7, qr->grid_size - 7); + + jiggle_perspective(q, index); +} + +/* Rotate the capstone with so that corner 0 is the leftmost with respect + * to the given reference line. + */ +static void rotate_capstone(struct quirc_capstone *cap, + const struct quirc_point *h0, + const struct quirc_point *hd) +{ + struct quirc_point copy[4]; + int j; + int best = 0; + int best_score = INT_MAX; + + for (j = 0; j < 4; j++) { + struct quirc_point *p = &cap->corners[j]; + int score = (p->x - h0->x) * -hd->y + + (p->y - h0->y) * hd->x; + + if (!j || score < best_score) { + best = j; + best_score = score; + } + } + + /* Rotate the capstone */ + for (j = 0; j < 4; j++) + memcpy(©[j], &cap->corners[(j + best) % 4], + sizeof(copy[j])); + memcpy(cap->corners, copy, sizeof(cap->corners)); + perspective_setup(cap->c, cap->corners, 7.0, 7.0); +} + +static void record_qr_grid(struct quirc *q, int a, int b, int c) +{ + struct quirc_point h0, hd; + int i; + int qr_index; + struct quirc_grid *qr; + + if (q->num_grids >= QUIRC_MAX_GRIDS) + return; + + /* Construct the hypotenuse line from A to C. B should be to + * the left of this line. + */ + memcpy(&h0, &q->capstones[a].center, sizeof(h0)); + hd.x = q->capstones[c].center.x - q->capstones[a].center.x; + hd.y = q->capstones[c].center.y - q->capstones[a].center.y; + + /* Make sure A-B-C is clockwise */ + if ((q->capstones[b].center.x - h0.x) * -hd.y + + (q->capstones[b].center.y - h0.y) * hd.x > 0) { + int swap = a; + + a = c; + c = swap; + hd.x = -hd.x; + hd.y = -hd.y; + } + + /* Record the grid and its components */ + qr_index = q->num_grids; + qr = &q->grids[q->num_grids++]; + + memset(qr, 0, sizeof(*qr)); + qr->caps[0] = a; + qr->caps[1] = b; + qr->caps[2] = c; + qr->align_region = -1; + + /* Rotate each capstone so that corner 0 is top-left with respect + * to the grid. + */ + for (i = 0; i < 3; i++) { + struct quirc_capstone *cap = &q->capstones[qr->caps[i]]; + + rotate_capstone(cap, &h0, &hd); + cap->qr_grid = qr_index; + } + + /* Check the timing pattern by measuring grid size. This doesn't require a perspective + * transform. + */ + measure_grid_size(q, qr_index); + /* Make an estimate based for the alignment pattern based on extending + * lines from capstones A and C. + */ + if (!line_intersect(&q->capstones[a].corners[0], + &q->capstones[a].corners[1], + &q->capstones[c].corners[0], + &q->capstones[c].corners[3], + &qr->align)) + goto fail; + + /* On V2+ grids, we should use the alignment pattern. */ + if (qr->grid_size > 21) { + /* Try to find the actual location of the alignment pattern. */ + find_alignment_pattern(q, qr_index); + + /* Find the point of the alignment pattern closest to the + * top-left of the QR grid. + */ + if (qr->align_region >= 0) { + struct polygon_score_data psd; + struct quirc_region *reg = + &q->regions[qr->align_region]; + + /* Start from some point inside the alignment pattern */ + memcpy(&qr->align, ®->seed, sizeof(qr->align)); + + memcpy(&psd.ref, &hd, sizeof(psd.ref)); + psd.corners = &qr->align; + psd.scores[0] = -hd.y * qr->align.x + + hd.x * qr->align.y; + + flood_fill_seed(q, reg->seed.x, reg->seed.y, + qr->align_region, QUIRC_PIXEL_BLACK, + NULL, NULL); + flood_fill_seed(q, reg->seed.x, reg->seed.y, + QUIRC_PIXEL_BLACK, qr->align_region, + find_leftmost_to_line, &psd); + } + } + + setup_qr_perspective(q, qr_index); + return; + +fail: + /* We've been unable to complete setup for this grid. Undo what we've + * recorded and pretend it never happened. + */ + for (i = 0; i < 3; i++) + q->capstones[qr->caps[i]].qr_grid = -1; + q->num_grids--; +} + +struct neighbour { + int index; + float distance; +}; + +struct neighbour_list { + struct neighbour n[QUIRC_MAX_CAPSTONES]; + int count; +}; + +static void test_neighbours(struct quirc *q, int i, + const struct neighbour_list *hlist, + const struct neighbour_list *vlist) +{ + /* Test each possible grouping */ + for (int j = 0; j < hlist->count; j++) { + const struct neighbour *hn = &hlist->n[j]; + for (int k = 0; k < vlist->count; k++) { + const struct neighbour *vn = &vlist->n[k]; + float squareness = fabsf(1.0f - hn->distance / vn->distance); + if (squareness < 0.2f) + record_qr_grid(q, hn->index, i, vn->index); + } + } +} + +static void test_grouping(struct quirc *q, unsigned int i) +{ + struct quirc_capstone *c1 = &q->capstones[i]; + int j; + struct neighbour_list hlist; + struct neighbour_list vlist; + + hlist.count = 0; + vlist.count = 0; + + /* Look for potential neighbours by examining the relative gradients + * from this capstone to others. + */ + for (j = 0; j < q->num_capstones; j++) { + struct quirc_capstone *c2 = &q->capstones[j]; + float u, v; + + if (i == (unsigned)j) + continue; + + perspective_unmap(c1->c, &c2->center, &u, &v); + + u = fabsf(u - 3.5f); + v = fabsf(v - 3.5f); + + if (u < 0.2f * v) { + struct neighbour *n = &hlist.n[hlist.count++]; + + n->index = j; + n->distance = v; + } + + if (v < 0.2f * u) { + struct neighbour *n = &vlist.n[vlist.count++]; + + n->index = j; + n->distance = u; + } + } + + if (!(hlist.count && vlist.count)) + return; + + test_neighbours(q, i, &hlist, &vlist); +} + +static void pixels_setup(struct quirc *q, uint8_t threshold) +{ + if (QUIRC_PIXEL_ALIAS_IMAGE) { + q->pixels = (quirc_pixel_t *)q->image; + } + + uint8_t* source = q->image; + quirc_pixel_t* dest = q->pixels; + int length = q->w * q->h; + while (length--) { + uint8_t value = *source++; + *dest++ = (value < threshold) ? QUIRC_PIXEL_BLACK : QUIRC_PIXEL_WHITE; + } +} + +uint8_t *quirc_begin(struct quirc *q, int *w, int *h) +{ + q->num_regions = QUIRC_PIXEL_REGION; + q->num_capstones = 0; + q->num_grids = 0; + + if (w) + *w = q->w; + if (h) + *h = q->h; + + return q->image; +} + +void quirc_end(struct quirc *q) +{ + int i; + + uint8_t threshold = otsu(q); + pixels_setup(q, threshold); + + for (i = 0; i < q->h; i++) + finder_scan(q, i); + + for (i = 0; i < q->num_capstones; i++) + test_grouping(q, i); +} + +void quirc_extract(const struct quirc *q, int index, + struct quirc_code *code) +{ + const struct quirc_grid *qr = &q->grids[index]; + int y; + int i = 0; + + if (index < 0 || index > q->num_grids) + return; + + memset(code, 0, sizeof(*code)); + + perspective_map(qr->c, 0.0, 0.0, &code->corners[0]); + perspective_map(qr->c, qr->grid_size, 0.0, &code->corners[1]); + perspective_map(qr->c, qr->grid_size, qr->grid_size, + &code->corners[2]); + perspective_map(qr->c, 0.0, qr->grid_size, &code->corners[3]); + + code->size = qr->grid_size; + + for (y = 0; y < qr->grid_size; y++) { + int x; + for (x = 0; x < qr->grid_size; x++) { + if (read_cell(q, index, x, y) > 0) { + code->cell_bitmap[i >> 3] |= (1 << (i & 7)); + } + i++; + } + } +} diff --git a/circuitpython/lib/quirc/lib/quirc.c b/circuitpython/lib/quirc/lib/quirc.c new file mode 100644 index 0000000..23c17dc --- /dev/null +++ b/circuitpython/lib/quirc/lib/quirc.c @@ -0,0 +1,165 @@ +/* quirc -- QR-code recognition library + * Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <stdlib.h> +#include <string.h> +#include "quirc_internal.h" + +const char *quirc_version(void) +{ + return "1.0"; +} + +struct quirc *quirc_new(void) +{ + struct quirc *q = QUIRC_MALLOC(sizeof(*q)); + + if (!q) + return NULL; + + memset(q, 0, sizeof(*q)); + return q; +} + +void quirc_destroy(struct quirc *q) +{ + QUIRC_FREE(q->image); + /* q->pixels may alias q->image when their type representation is of the + same size, so we need to be careful here to avoid a double QUIRC_FREE */ + if (!QUIRC_PIXEL_ALIAS_IMAGE) + QUIRC_FREE(q->pixels); + QUIRC_FREE(q->flood_fill_vars); + QUIRC_FREE(q); +} + +int quirc_resize(struct quirc *q, int w, int h) +{ + uint8_t *image = NULL; + quirc_pixel_t *pixels = NULL; + size_t num_vars; + size_t vars_byte_size; + struct quirc_flood_fill_vars *vars = NULL; + + /* + * XXX: w and h should be size_t (or at least unsigned) as negatives + * values would not make much sense. The downside is that it would break + * both the API and ABI. Thus, at the moment, let's just do a sanity + * check. + */ + if (w < 0 || h < 0) + goto fail; + + /* + * alloc a new buffer for q->image. We avoid realloc(3) because we want + * on failure to be leave `q` in a consistant, unmodified state. + */ + image = QUIRC_CALLOC(w, h); + if (!image) + goto fail; + + /* compute the "old" (i.e. currently allocated) and the "new" + (i.e. requested) image dimensions */ + size_t olddim = q->w * q->h; + size_t newdim = w * h; + size_t min = (olddim < newdim ? olddim : newdim); + + /* + * copy the data into the new buffer, avoiding (a) to read beyond the + * old buffer when the new size is greater and (b) to write beyond the + * new buffer when the new size is smaller, hence the min computation. + */ + (void)memcpy(image, q->image, min); + + /* alloc a new buffer for q->pixels if needed */ + if (!QUIRC_PIXEL_ALIAS_IMAGE) { + pixels = QUIRC_CALLOC(newdim, sizeof(quirc_pixel_t)); + if (!pixels) + goto fail; + } + + /* + * alloc the work area for the flood filling logic. + * + * the size was chosen with the following assumptions and observations: + * + * - rings are the regions which requires the biggest work area. + * - they consumes the most when they are rotated by about 45 degree. + * in that case, the necessary depth is about (2 * height_of_the_ring). + * - the maximum height of rings would be about 1/3 of the image height. + */ + + if ((size_t)h * 2 / 2 != (size_t)h) { + goto fail; /* size_t overflow */ + } + num_vars = (size_t)h * 2 / 3; + if (num_vars == 0) { + num_vars = 1; + } + + vars_byte_size = sizeof(*vars) * num_vars; + if (vars_byte_size / sizeof(*vars) != num_vars) { + goto fail; /* size_t overflow */ + } + vars = QUIRC_MALLOC(vars_byte_size); + if (!vars) + goto fail; + + /* alloc succeeded, update `q` with the new size and buffers */ + q->w = w; + q->h = h; + QUIRC_FREE(q->image); + q->image = image; + if (!QUIRC_PIXEL_ALIAS_IMAGE) { + QUIRC_FREE(q->pixels); + q->pixels = pixels; + } + QUIRC_FREE(q->flood_fill_vars); + q->flood_fill_vars = vars; + q->num_flood_fill_vars = num_vars; + + return 0; + /* NOTREACHED */ +fail: + QUIRC_FREE(image); + QUIRC_FREE(pixels); + QUIRC_FREE(vars); + + return -1; +} + +int quirc_count(const struct quirc *q) +{ + return q->num_grids; +} + +static const char *const error_table[] = { + [QUIRC_SUCCESS] = "Success", + [QUIRC_ERROR_INVALID_GRID_SIZE] = "Invalid grid size", + [QUIRC_ERROR_INVALID_VERSION] = "Invalid version", + [QUIRC_ERROR_FORMAT_ECC] = "Format data ECC failure", + [QUIRC_ERROR_DATA_ECC] = "ECC failure", + [QUIRC_ERROR_UNKNOWN_DATA_TYPE] = "Unknown data type", + [QUIRC_ERROR_DATA_OVERFLOW] = "Data overflow", + [QUIRC_ERROR_DATA_UNDERFLOW] = "Data underflow" +}; + +const char *quirc_strerror(quirc_decode_error_t err) +{ + if (err >= 0 && err < sizeof(error_table) / sizeof(error_table[0])) + return error_table[err]; + + return "Unknown error"; +} diff --git a/circuitpython/lib/quirc/lib/quirc.h b/circuitpython/lib/quirc/lib/quirc.h new file mode 100644 index 0000000..d8d250d --- /dev/null +++ b/circuitpython/lib/quirc/lib/quirc.h @@ -0,0 +1,178 @@ +/* quirc -- QR-code recognition library + * Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#ifndef QUIRC_H_ +#define QUIRC_H_ + +#include <stdint.h> + +#ifdef __cplusplus +extern "C" { +#endif + +struct quirc; + +/* Obtain the library version string. */ +const char *quirc_version(void); + +/* Construct a new QR-code recognizer. This function will return NULL + * if sufficient memory could not be allocated. + */ +struct quirc *quirc_new(void); + +/* Destroy a QR-code recognizer. */ +void quirc_destroy(struct quirc *q); + +/* Resize the QR-code recognizer. The size of an image must be + * specified before codes can be analyzed. + * + * This function returns 0 on success, or -1 if sufficient memory could + * not be allocated. + */ +int quirc_resize(struct quirc *q, int w, int h); + +/* These functions are used to process images for QR-code recognition. + * quirc_begin() must first be called to obtain access to a buffer into + * which the input image should be placed. Optionally, the current + * width and height may be returned. + * + * After filling the buffer, quirc_end() should be called to process + * the image for QR-code recognition. The locations and content of each + * code may be obtained using accessor functions described below. + */ +uint8_t *quirc_begin(struct quirc *q, int *w, int *h); +void quirc_end(struct quirc *q); + +/* This structure describes a location in the input image buffer. */ +struct quirc_point { + int x; + int y; +}; + +/* This enum describes the various decoder errors which may occur. */ +typedef enum { + QUIRC_SUCCESS = 0, + QUIRC_ERROR_INVALID_GRID_SIZE, + QUIRC_ERROR_INVALID_VERSION, + QUIRC_ERROR_FORMAT_ECC, + QUIRC_ERROR_DATA_ECC, + QUIRC_ERROR_UNKNOWN_DATA_TYPE, + QUIRC_ERROR_DATA_OVERFLOW, + QUIRC_ERROR_DATA_UNDERFLOW +} quirc_decode_error_t; + +/* Return a string error message for an error code. */ +const char *quirc_strerror(quirc_decode_error_t err); + +/* Limits on the maximum size of QR-codes and their content. */ +#define QUIRC_MAX_VERSION 40 +#define QUIRC_MAX_GRID_SIZE (QUIRC_MAX_VERSION * 4 + 17) +#define QUIRC_MAX_BITMAP (((QUIRC_MAX_GRID_SIZE * QUIRC_MAX_GRID_SIZE) + 7) / 8) +#define QUIRC_MAX_PAYLOAD 8896 + +/* QR-code ECC types. */ +#define QUIRC_ECC_LEVEL_M 0 +#define QUIRC_ECC_LEVEL_L 1 +#define QUIRC_ECC_LEVEL_H 2 +#define QUIRC_ECC_LEVEL_Q 3 + +/* QR-code data types. */ +#define QUIRC_DATA_TYPE_NUMERIC 1 +#define QUIRC_DATA_TYPE_ALPHA 2 +#define QUIRC_DATA_TYPE_BYTE 4 +#define QUIRC_DATA_TYPE_KANJI 8 + +/* Common character encodings */ +#define QUIRC_ECI_ISO_8859_1 1 +#define QUIRC_ECI_IBM437 2 +#define QUIRC_ECI_ISO_8859_2 4 +#define QUIRC_ECI_ISO_8859_3 5 +#define QUIRC_ECI_ISO_8859_4 6 +#define QUIRC_ECI_ISO_8859_5 7 +#define QUIRC_ECI_ISO_8859_6 8 +#define QUIRC_ECI_ISO_8859_7 9 +#define QUIRC_ECI_ISO_8859_8 10 +#define QUIRC_ECI_ISO_8859_9 11 +#define QUIRC_ECI_WINDOWS_874 13 +#define QUIRC_ECI_ISO_8859_13 15 +#define QUIRC_ECI_ISO_8859_15 17 +#define QUIRC_ECI_SHIFT_JIS 20 +#define QUIRC_ECI_UTF_8 26 + +/* This structure is used to return information about detected QR codes + * in the input image. + */ +struct quirc_code { + /* The four corners of the QR-code, from top left, clockwise */ + struct quirc_point corners[4]; + + /* The number of cells across in the QR-code. The cell bitmap + * is a bitmask giving the actual values of cells. If the cell + * at (x, y) is black, then the following bit is set: + * + * cell_bitmap[i >> 3] & (1 << (i & 7)) + * + * where i = (y * size) + x. + */ + int size; + uint8_t cell_bitmap[QUIRC_MAX_BITMAP]; +}; + +/* This structure holds the decoded QR-code data */ +struct quirc_data { + /* Various parameters of the QR-code. These can mostly be + * ignored if you only care about the data. + */ + int version; + int ecc_level; + int mask; + + /* This field is the highest-valued data type found in the QR + * code. + */ + int data_type; + + /* Data payload. For the Kanji datatype, payload is encoded as + * Shift-JIS. For all other datatypes, payload is ASCII text. + */ + uint8_t payload[QUIRC_MAX_PAYLOAD]; + int payload_len; + + /* ECI assignment number */ + uint32_t eci; +}; + +/* Return the number of QR-codes identified in the last processed + * image. + */ +int quirc_count(const struct quirc *q); + +/* Extract the QR-code specified by the given index. */ +void quirc_extract(const struct quirc *q, int index, + struct quirc_code *code); + +/* Decode a QR-code, returning the payload data. */ +quirc_decode_error_t quirc_decode(const struct quirc_code *code, + struct quirc_data *data); + +/* Flip a QR-code according to optional mirror feature of ISO 18004:2015 */ +void quirc_flip(struct quirc_code *code); + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/circuitpython/lib/quirc/lib/quirc_internal.h b/circuitpython/lib/quirc/lib/quirc_internal.h new file mode 100644 index 0000000..25ae91b --- /dev/null +++ b/circuitpython/lib/quirc/lib/quirc_internal.h @@ -0,0 +1,145 @@ +/* quirc -- QR-code recognition library + * Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#ifndef QUIRC_INTERNAL_H_ +#define QUIRC_INTERNAL_H_ + +#include <assert.h> +#include <stdlib.h> + +#include "quirc.h" + +#define QUIRC_ASSERT(a) assert(a) + +#define QUIRC_PIXEL_WHITE 0 +#define QUIRC_PIXEL_BLACK 1 +#define QUIRC_PIXEL_REGION 2 + +#ifndef QUIRC_MAX_REGIONS +#define QUIRC_MAX_REGIONS 254 +#endif +#define QUIRC_MAX_CAPSTONES 32 +#define QUIRC_MAX_GRIDS (QUIRC_MAX_CAPSTONES * 2) + +#define QUIRC_PERSPECTIVE_PARAMS 8 + +#if QUIRC_MAX_REGIONS < UINT8_MAX +#define QUIRC_PIXEL_ALIAS_IMAGE 1 +typedef uint8_t quirc_pixel_t; +#elif QUIRC_MAX_REGIONS < UINT16_MAX +#define QUIRC_PIXEL_ALIAS_IMAGE 0 +typedef uint16_t quirc_pixel_t; +#else +#error "QUIRC_MAX_REGIONS > 65534 is not supported" +#endif + +struct quirc_region { + struct quirc_point seed; + int count; + int capstone; +}; + +struct quirc_capstone { + int ring; + int stone; + + struct quirc_point corners[4]; + struct quirc_point center; + float c[QUIRC_PERSPECTIVE_PARAMS]; + + int qr_grid; +}; + +struct quirc_grid { + /* Capstone indices */ + int caps[3]; + + /* Alignment pattern region and corner */ + int align_region; + struct quirc_point align; + + /* Timing pattern endpoints */ + struct quirc_point tpep[3]; + + /* Grid size and perspective transform */ + int grid_size; + float c[QUIRC_PERSPECTIVE_PARAMS]; +}; + +struct quirc_flood_fill_vars { + int y; + int right; + int left_up; + int left_down; +}; + +struct quirc { + uint8_t *image; + quirc_pixel_t *pixels; + int w; + int h; + + int num_regions; + struct quirc_region regions[QUIRC_MAX_REGIONS]; + + int num_capstones; + struct quirc_capstone capstones[QUIRC_MAX_CAPSTONES]; + + int num_grids; + struct quirc_grid grids[QUIRC_MAX_GRIDS]; + + size_t num_flood_fill_vars; + struct quirc_flood_fill_vars *flood_fill_vars; +}; + +/************************************************************************ + * QR-code version information database + */ + +#define QUIRC_MAX_VERSION 40 +#define QUIRC_MAX_ALIGNMENT 7 + +struct quirc_rs_params { + int bs; /* Small block size */ + int dw; /* Small data words */ + int ns; /* Number of small blocks */ +}; + +struct quirc_version_info { + int data_bytes; + int apat[QUIRC_MAX_ALIGNMENT]; + struct quirc_rs_params ecc[4]; +}; + +extern const struct quirc_version_info quirc_version_db[QUIRC_MAX_VERSION + 1]; + +#ifndef QUIRC_CALLOC +#define QUIRC_CALLOC(x,y) calloc((x),(y)) +#endif + +#ifndef QUIRC_MALLOC +#define QUIRC_MALLOC(x) malloc((x)) +#endif + +#ifndef QUIRC_FREE +#define QUIRC_FREE(x) free((x)) +#endif + +#ifndef QUIRC_SMALL_STACK +#define QUIRC_SMALL_STACK (0) +#endif + +#endif diff --git a/circuitpython/lib/quirc/lib/version_db.c b/circuitpython/lib/quirc/lib/version_db.c new file mode 100644 index 0000000..fea8146 --- /dev/null +++ b/circuitpython/lib/quirc/lib/version_db.c @@ -0,0 +1,421 @@ +/* quirc -- QR-code recognition library + * Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include "quirc_internal.h" + +const struct quirc_version_info quirc_version_db[QUIRC_MAX_VERSION + 1] = { + {0}, + { /* Version 1 */ + .data_bytes = 26, + .apat = {0}, + .ecc = { + {.bs = 26, .dw = 16, .ns = 1}, + {.bs = 26, .dw = 19, .ns = 1}, + {.bs = 26, .dw = 9, .ns = 1}, + {.bs = 26, .dw = 13, .ns = 1} + } + }, + { /* Version 2 */ + .data_bytes = 44, + .apat = {6, 18, 0}, + .ecc = { + {.bs = 44, .dw = 28, .ns = 1}, + {.bs = 44, .dw = 34, .ns = 1}, + {.bs = 44, .dw = 16, .ns = 1}, + {.bs = 44, .dw = 22, .ns = 1} + } + }, + { /* Version 3 */ + .data_bytes = 70, + .apat = {6, 22, 0}, + .ecc = { + {.bs = 70, .dw = 44, .ns = 1}, + {.bs = 70, .dw = 55, .ns = 1}, + {.bs = 35, .dw = 13, .ns = 2}, + {.bs = 35, .dw = 17, .ns = 2} + } + }, + { /* Version 4 */ + .data_bytes = 100, + .apat = {6, 26, 0}, + .ecc = { + {.bs = 50, .dw = 32, .ns = 2}, + {.bs = 100, .dw = 80, .ns = 1}, + {.bs = 25, .dw = 9, .ns = 4}, + {.bs = 50, .dw = 24, .ns = 2} + } + }, + { /* Version 5 */ + .data_bytes = 134, + .apat = {6, 30, 0}, + .ecc = { + {.bs = 67, .dw = 43, .ns = 2}, + {.bs = 134, .dw = 108, .ns = 1}, + {.bs = 33, .dw = 11, .ns = 2}, + {.bs = 33, .dw = 15, .ns = 2} + } + }, + { /* Version 6 */ + .data_bytes = 172, + .apat = {6, 34, 0}, + .ecc = { + {.bs = 43, .dw = 27, .ns = 4}, + {.bs = 86, .dw = 68, .ns = 2}, + {.bs = 43, .dw = 15, .ns = 4}, + {.bs = 43, .dw = 19, .ns = 4} + } + }, + { /* Version 7 */ + .data_bytes = 196, + .apat = {6, 22, 38, 0}, + .ecc = { + {.bs = 49, .dw = 31, .ns = 4}, + {.bs = 98, .dw = 78, .ns = 2}, + {.bs = 39, .dw = 13, .ns = 4}, + {.bs = 32, .dw = 14, .ns = 2} + } + }, + { /* Version 8 */ + .data_bytes = 242, + .apat = {6, 24, 42, 0}, + .ecc = { + {.bs = 60, .dw = 38, .ns = 2}, + {.bs = 121, .dw = 97, .ns = 2}, + {.bs = 40, .dw = 14, .ns = 4}, + {.bs = 40, .dw = 18, .ns = 4} + } + }, + { /* Version 9 */ + .data_bytes = 292, + .apat = {6, 26, 46, 0}, + .ecc = { + {.bs = 58, .dw = 36, .ns = 3}, + {.bs = 146, .dw = 116, .ns = 2}, + {.bs = 36, .dw = 12, .ns = 4}, + {.bs = 36, .dw = 16, .ns = 4} + } + }, + { /* Version 10 */ + .data_bytes = 346, + .apat = {6, 28, 50, 0}, + .ecc = { + {.bs = 69, .dw = 43, .ns = 4}, + {.bs = 86, .dw = 68, .ns = 2}, + {.bs = 43, .dw = 15, .ns = 6}, + {.bs = 43, .dw = 19, .ns = 6} + } + }, + { /* Version 11 */ + .data_bytes = 404, + .apat = {6, 30, 54, 0}, + .ecc = { + {.bs = 80, .dw = 50, .ns = 1}, + {.bs = 101, .dw = 81, .ns = 4}, + {.bs = 36, .dw = 12, .ns = 3}, + {.bs = 50, .dw = 22, .ns = 4} + } + }, + { /* Version 12 */ + .data_bytes = 466, + .apat = {6, 32, 58, 0}, + .ecc = { + {.bs = 58, .dw = 36, .ns = 6}, + {.bs = 116, .dw = 92, .ns = 2}, + {.bs = 42, .dw = 14, .ns = 7}, + {.bs = 46, .dw = 20, .ns = 4} + } + }, + { /* Version 13 */ + .data_bytes = 532, + .apat = {6, 34, 62, 0}, + .ecc = { + {.bs = 59, .dw = 37, .ns = 8}, + {.bs = 133, .dw = 107, .ns = 4}, + {.bs = 33, .dw = 11, .ns = 12}, + {.bs = 44, .dw = 20, .ns = 8} + } + }, + { /* Version 14 */ + .data_bytes = 581, + .apat = {6, 26, 46, 66, 0}, + .ecc = { + {.bs = 64, .dw = 40, .ns = 4}, + {.bs = 145, .dw = 115, .ns = 3}, + {.bs = 36, .dw = 12, .ns = 11}, + {.bs = 36, .dw = 16, .ns = 11} + } + }, + { /* Version 15 */ + .data_bytes = 655, + .apat = {6, 26, 48, 70, 0}, + .ecc = { + {.bs = 65, .dw = 41, .ns = 5}, + {.bs = 109, .dw = 87, .ns = 5}, + {.bs = 36, .dw = 12, .ns = 11}, + {.bs = 54, .dw = 24, .ns = 5} + } + }, + { /* Version 16 */ + .data_bytes = 733, + .apat = {6, 26, 50, 74, 0}, + .ecc = { + {.bs = 73, .dw = 45, .ns = 7}, + {.bs = 122, .dw = 98, .ns = 5}, + {.bs = 45, .dw = 15, .ns = 3}, + {.bs = 43, .dw = 19, .ns = 15} + } + }, + { /* Version 17 */ + .data_bytes = 815, + .apat = {6, 30, 54, 78, 0}, + .ecc = { + {.bs = 74, .dw = 46, .ns = 10}, + {.bs = 135, .dw = 107, .ns = 1}, + {.bs = 42, .dw = 14, .ns = 2}, + {.bs = 50, .dw = 22, .ns = 1} + } + }, + { /* Version 18 */ + .data_bytes = 901, + .apat = {6, 30, 56, 82, 0}, + .ecc = { + {.bs = 69, .dw = 43, .ns = 9}, + {.bs = 150, .dw = 120, .ns = 5}, + {.bs = 42, .dw = 14, .ns = 2}, + {.bs = 50, .dw = 22, .ns = 17} + } + }, + { /* Version 19 */ + .data_bytes = 991, + .apat = {6, 30, 58, 86, 0}, + .ecc = { + {.bs = 70, .dw = 44, .ns = 3}, + {.bs = 141, .dw = 113, .ns = 3}, + {.bs = 39, .dw = 13, .ns = 9}, + {.bs = 47, .dw = 21, .ns = 17} + } + }, + { /* Version 20 */ + .data_bytes = 1085, + .apat = {6, 34, 62, 90, 0}, + .ecc = { + {.bs = 67, .dw = 41, .ns = 3}, + {.bs = 135, .dw = 107, .ns = 3}, + {.bs = 43, .dw = 15, .ns = 15}, + {.bs = 54, .dw = 24, .ns = 15} + } + }, + { /* Version 21 */ + .data_bytes = 1156, + .apat = {6, 28, 50, 72, 92, 0}, + .ecc = { + {.bs = 68, .dw = 42, .ns = 17}, + {.bs = 144, .dw = 116, .ns = 4}, + {.bs = 46, .dw = 16, .ns = 19}, + {.bs = 50, .dw = 22, .ns = 17} + } + }, + { /* Version 22 */ + .data_bytes = 1258, + .apat = {6, 26, 50, 74, 98, 0}, + .ecc = { + {.bs = 74, .dw = 46, .ns = 17}, + {.bs = 139, .dw = 111, .ns = 2}, + {.bs = 37, .dw = 13, .ns = 34}, + {.bs = 54, .dw = 24, .ns = 7} + } + }, + { /* Version 23 */ + .data_bytes = 1364, + .apat = {6, 30, 54, 78, 102, 0}, + .ecc = { + {.bs = 75, .dw = 47, .ns = 4}, + {.bs = 151, .dw = 121, .ns = 4}, + {.bs = 45, .dw = 15, .ns = 16}, + {.bs = 54, .dw = 24, .ns = 11} + } + }, + { /* Version 24 */ + .data_bytes = 1474, + .apat = {6, 28, 54, 80, 106, 0}, + .ecc = { + {.bs = 73, .dw = 45, .ns = 6}, + {.bs = 147, .dw = 117, .ns = 6}, + {.bs = 46, .dw = 16, .ns = 30}, + {.bs = 54, .dw = 24, .ns = 11} + } + }, + { /* Version 25 */ + .data_bytes = 1588, + .apat = {6, 32, 58, 84, 110, 0}, + .ecc = { + {.bs = 75, .dw = 47, .ns = 8}, + {.bs = 132, .dw = 106, .ns = 8}, + {.bs = 45, .dw = 15, .ns = 22}, + {.bs = 54, .dw = 24, .ns = 7} + } + }, + { /* Version 26 */ + .data_bytes = 1706, + .apat = {6, 30, 58, 86, 114, 0}, + .ecc = { + {.bs = 74, .dw = 46, .ns = 19}, + {.bs = 142, .dw = 114, .ns = 10}, + {.bs = 46, .dw = 16, .ns = 33}, + {.bs = 50, .dw = 22, .ns = 28} + } + }, + { /* Version 27 */ + .data_bytes = 1828, + .apat = {6, 34, 62, 90, 118, 0}, + .ecc = { + {.bs = 73, .dw = 45, .ns = 22}, + {.bs = 152, .dw = 122, .ns = 8}, + {.bs = 45, .dw = 15, .ns = 12}, + {.bs = 53, .dw = 23, .ns = 8} + } + }, + { /* Version 28 */ + .data_bytes = 1921, + .apat = {6, 26, 50, 74, 98, 122, 0}, + .ecc = { + {.bs = 73, .dw = 45, .ns = 3}, + {.bs = 147, .dw = 117, .ns = 3}, + {.bs = 45, .dw = 15, .ns = 11}, + {.bs = 54, .dw = 24, .ns = 4} + } + }, + { /* Version 29 */ + .data_bytes = 2051, + .apat = {6, 30, 54, 78, 102, 126, 0}, + .ecc = { + {.bs = 73, .dw = 45, .ns = 21}, + {.bs = 146, .dw = 116, .ns = 7}, + {.bs = 45, .dw = 15, .ns = 19}, + {.bs = 53, .dw = 23, .ns = 1} + } + }, + { /* Version 30 */ + .data_bytes = 2185, + .apat = {6, 26, 52, 78, 104, 130, 0}, + .ecc = { + {.bs = 75, .dw = 47, .ns = 19}, + {.bs = 145, .dw = 115, .ns = 5}, + {.bs = 45, .dw = 15, .ns = 23}, + {.bs = 54, .dw = 24, .ns = 15} + } + }, + { /* Version 31 */ + .data_bytes = 2323, + .apat = {6, 30, 56, 82, 108, 134, 0}, + .ecc = { + {.bs = 74, .dw = 46, .ns = 2}, + {.bs = 145, .dw = 115, .ns = 13}, + {.bs = 45, .dw = 15, .ns = 23}, + {.bs = 54, .dw = 24, .ns = 42} + } + }, + { /* Version 32 */ + .data_bytes = 2465, + .apat = {6, 34, 60, 86, 112, 138, 0}, + .ecc = { + {.bs = 74, .dw = 46, .ns = 10}, + {.bs = 145, .dw = 115, .ns = 17}, + {.bs = 45, .dw = 15, .ns = 19}, + {.bs = 54, .dw = 24, .ns = 10} + } + }, + { /* Version 33 */ + .data_bytes = 2611, + .apat = {6, 30, 58, 86, 114, 142, 0}, + .ecc = { + {.bs = 74, .dw = 46, .ns = 14}, + {.bs = 145, .dw = 115, .ns = 17}, + {.bs = 45, .dw = 15, .ns = 11}, + {.bs = 54, .dw = 24, .ns = 29} + } + }, + { /* Version 34 */ + .data_bytes = 2761, + .apat = {6, 34, 62, 90, 118, 146, 0}, + .ecc = { + {.bs = 74, .dw = 46, .ns = 14}, + {.bs = 145, .dw = 115, .ns = 13}, + {.bs = 46, .dw = 16, .ns = 59}, + {.bs = 54, .dw = 24, .ns = 44} + } + }, + { /* Version 35 */ + .data_bytes = 2876, + .apat = {6, 30, 54, 78, 102, 126, 150}, + .ecc = { + {.bs = 75, .dw = 47, .ns = 12}, + {.bs = 151, .dw = 121, .ns = 12}, + {.bs = 45, .dw = 15, .ns = 22}, + {.bs = 54, .dw = 24, .ns = 39} + } + }, + { /* Version 36 */ + .data_bytes = 3034, + .apat = {6, 24, 50, 76, 102, 128, 154}, + .ecc = { + {.bs = 75, .dw = 47, .ns = 6}, + {.bs = 151, .dw = 121, .ns = 6}, + {.bs = 45, .dw = 15, .ns = 2}, + {.bs = 54, .dw = 24, .ns = 46} + } + }, + { /* Version 37 */ + .data_bytes = 3196, + .apat = {6, 28, 54, 80, 106, 132, 158}, + .ecc = { + {.bs = 74, .dw = 46, .ns = 29}, + {.bs = 152, .dw = 122, .ns = 17}, + {.bs = 45, .dw = 15, .ns = 24}, + {.bs = 54, .dw = 24, .ns = 49} + } + }, + { /* Version 38 */ + .data_bytes = 3362, + .apat = {6, 32, 58, 84, 110, 136, 162}, + .ecc = { + {.bs = 74, .dw = 46, .ns = 13}, + {.bs = 152, .dw = 122, .ns = 4}, + {.bs = 45, .dw = 15, .ns = 42}, + {.bs = 54, .dw = 24, .ns = 48} + } + }, + { /* Version 39 */ + .data_bytes = 3532, + .apat = {6, 26, 54, 82, 110, 138, 166}, + .ecc = { + {.bs = 75, .dw = 47, .ns = 40}, + {.bs = 147, .dw = 117, .ns = 20}, + {.bs = 45, .dw = 15, .ns = 10}, + {.bs = 54, .dw = 24, .ns = 43} + } + }, + { /* Version 40 */ + .data_bytes = 3706, + .apat = {6, 30, 58, 86, 114, 142, 170}, + .ecc = { + {.bs = 75, .dw = 47, .ns = 18}, + {.bs = 148, .dw = 118, .ns = 19}, + {.bs = 45, .dw = 15, .ns = 20}, + {.bs = 54, .dw = 24, .ns = 34} + } + } +}; diff --git a/circuitpython/lib/quirc/tests/dbgutil.c b/circuitpython/lib/quirc/tests/dbgutil.c new file mode 100644 index 0000000..c023d91 --- /dev/null +++ b/circuitpython/lib/quirc/tests/dbgutil.c @@ -0,0 +1,307 @@ +/* quirc -- QR-code recognition library + * Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include <jpeglib.h> +#include <png.h> + +#include <quirc.h> + +#include "dbgutil.h" + +static const char *data_type_str(int dt) +{ + switch (dt) { + case QUIRC_DATA_TYPE_NUMERIC: return "NUMERIC"; + case QUIRC_DATA_TYPE_ALPHA: return "ALPHA"; + case QUIRC_DATA_TYPE_BYTE: return "BYTE"; + case QUIRC_DATA_TYPE_KANJI: return "KANJI"; + } + + return "unknown"; +} + +void dump_data(const struct quirc_data *data) +{ + printf(" Version: %d\n", data->version); + printf(" ECC level: %c\n", "MLHQ"[data->ecc_level]); + printf(" Mask: %d\n", data->mask); + printf(" Data type: %d (%s)\n", + data->data_type, data_type_str(data->data_type)); + printf(" Length: %d\n", data->payload_len); + printf(" Payload: %s\n", data->payload); + + if (data->eci) + printf(" ECI: %d\n", data->eci); +} + +void dump_cells(const struct quirc_code *code) +{ + int u, v; + + printf(" %d cells, corners:", code->size); + for (u = 0; u < 4; u++) + printf(" (%d,%d)", code->corners[u].x, + code->corners[u].y); + printf("\n"); + + for (v = 0; v < code->size; v++) { + printf(" "); + for (u = 0; u < code->size; u++) { + int p = v * code->size + u; + + if (code->cell_bitmap[p >> 3] & (1 << (p & 7))) + printf("[]"); + else + printf(" "); + } + printf("\n"); + } +} + +struct my_jpeg_error { + struct jpeg_error_mgr base; + jmp_buf env; +}; + +static void my_output_message(struct jpeg_common_struct *com) +{ + struct my_jpeg_error *err = (struct my_jpeg_error *)com->err; + char buf[JMSG_LENGTH_MAX]; + + err->base.format_message(com, buf); + fprintf(stderr, "JPEG error: %s\n", buf); +} + +static void my_error_exit(struct jpeg_common_struct *com) +{ + struct my_jpeg_error *err = (struct my_jpeg_error *)com->err; + + my_output_message(com); + longjmp(err->env, 0); +} + +static struct jpeg_error_mgr *my_error_mgr(struct my_jpeg_error *err) +{ + jpeg_std_error(&err->base); + + err->base.error_exit = my_error_exit; + err->base.output_message = my_output_message; + + return &err->base; +} + +int load_jpeg(struct quirc *q, const char *filename) +{ + FILE *infile = fopen(filename, "rb"); + struct jpeg_decompress_struct dinfo; + struct my_jpeg_error err; + uint8_t *image; + int y; + + if (!infile) { + perror("can't open input file"); + return -1; + } + + memset(&dinfo, 0, sizeof(dinfo)); + dinfo.err = my_error_mgr(&err); + + if (setjmp(err.env)) + goto fail; + + jpeg_create_decompress(&dinfo); + jpeg_stdio_src(&dinfo, infile); + + jpeg_read_header(&dinfo, TRUE); + dinfo.output_components = 1; + dinfo.out_color_space = JCS_GRAYSCALE; + jpeg_start_decompress(&dinfo); + + if (dinfo.output_components != 1) { + fprintf(stderr, "Unexpected number of output components: %d", + dinfo.output_components); + goto fail; + } + + if (quirc_resize(q, dinfo.output_width, dinfo.output_height) < 0) + goto fail; + + image = quirc_begin(q, NULL, NULL); + + for (y = 0; y < dinfo.output_height; y++) { + JSAMPROW row_pointer = image + y * dinfo.output_width; + + jpeg_read_scanlines(&dinfo, &row_pointer, 1); + } + + jpeg_finish_decompress(&dinfo); + fclose(infile); + jpeg_destroy_decompress(&dinfo); + return 0; + +fail: + fclose(infile); + jpeg_destroy_decompress(&dinfo); + return -1; +} + +/* hacked from https://dev.w3.org/Amaya/libpng/example.c + * + * Check if a file is a PNG image using png_sig_cmp(). Returns 1 if the given + * file is a PNG and 0 otherwise. + */ +#define PNG_BYTES_TO_CHECK 4 +int check_if_png(const char *filename) +{ + int ret = 0; + FILE *infile = NULL; + unsigned char buf[PNG_BYTES_TO_CHECK]; + + /* Open the prospective PNG file. */ + if ((infile = fopen(filename, "rb")) == NULL) + goto out; + + /* Read in some of the signature bytes */ + if (fread(buf, 1, PNG_BYTES_TO_CHECK, infile) != PNG_BYTES_TO_CHECK) + goto out; + + /* + * Compare the first PNG_BYTES_TO_CHECK bytes of the signature. + * png_sig_cmp() returns zero if the image is a PNG and nonzero if it + * isn't a PNG. + */ + if (png_sig_cmp(buf, (png_size_t)0, PNG_BYTES_TO_CHECK) == 0) + ret = 1; + + /* FALLTHROUGH */ +out: + if (infile) + fclose(infile); + return (ret); +} + +int load_png(struct quirc *q, const char *filename) +{ + int width, height, rowbytes, interlace_type, number_passes = 1; + png_uint_32 trns; + png_byte color_type, bit_depth; + png_structp png_ptr = NULL; + png_infop info_ptr = NULL; + FILE *infile = NULL; + uint8_t *image; + int ret = -1; + int pass; + + if ((infile = fopen(filename, "rb")) == NULL) + goto out; + + png_ptr = png_create_read_struct(PNG_LIBPNG_VER_STRING, NULL, NULL, NULL); + if (!png_ptr) + goto out; + + info_ptr = png_create_info_struct(png_ptr); + if (!info_ptr) + goto out; + + if (setjmp(png_jmpbuf(png_ptr))) + goto out; + + png_init_io(png_ptr, infile); + + png_read_info(png_ptr, info_ptr); + + color_type = png_get_color_type(png_ptr, info_ptr); + bit_depth = png_get_bit_depth(png_ptr, info_ptr); + interlace_type = png_get_interlace_type(png_ptr, info_ptr); + + // Read any color_type into 8bit depth, Grayscale format. + // See http://www.libpng.org/pub/png/libpng-manual.txt + + // PNG_COLOR_TYPE_GRAY_ALPHA is always 8 or 16bit depth. + if (color_type == PNG_COLOR_TYPE_GRAY && bit_depth < 8) + png_set_expand_gray_1_2_4_to_8(png_ptr); + + if ((trns = png_get_valid(png_ptr, info_ptr, PNG_INFO_tRNS))) + png_set_tRNS_to_alpha(png_ptr); + + if (bit_depth == 16) +#if PNG_LIBPNG_VER >= 10504 + png_set_scale_16(png_ptr); +#else + png_set_strip_16(png_ptr); +#endif + + if ((trns) || color_type & PNG_COLOR_MASK_ALPHA) + png_set_strip_alpha(png_ptr); + + if (color_type == PNG_COLOR_TYPE_PALETTE) + png_set_palette_to_rgb(png_ptr); + + if (color_type == PNG_COLOR_TYPE_PALETTE || + color_type == PNG_COLOR_TYPE_RGB || + color_type == PNG_COLOR_TYPE_RGB_ALPHA) { + png_set_rgb_to_gray_fixed(png_ptr, 1, -1, -1); + } + + if (interlace_type != PNG_INTERLACE_NONE) + number_passes = png_set_interlace_handling(png_ptr); + + png_read_update_info(png_ptr, info_ptr); + + width = png_get_image_width(png_ptr, info_ptr); + height = png_get_image_height(png_ptr, info_ptr); + rowbytes = png_get_rowbytes(png_ptr, info_ptr); + if (rowbytes != width) { + fprintf(stderr, + "load_png: expected rowbytes to be %u but got %u\n", + width, rowbytes); + goto out; + } + + if (quirc_resize(q, width, height) < 0) + goto out; + + image = quirc_begin(q, NULL, NULL); + + for (pass = 0; pass < number_passes; pass++) { + int y; + + for (y = 0; y < height; y++) { + png_bytep row_pointer = image + y * width; + png_read_rows(png_ptr, &row_pointer, NULL, 1); + } + } + + png_read_end(png_ptr, info_ptr); + + ret = 0; + /* FALLTHROUGH */ +out: + /* cleanup */ + if (png_ptr) { + if (info_ptr) + png_destroy_read_struct(&png_ptr, &info_ptr, (png_infopp)NULL); + else + png_destroy_read_struct(&png_ptr, (png_infopp)NULL, (png_infopp)NULL); + } + if (infile) + fclose(infile); + return (ret); +} diff --git a/circuitpython/lib/quirc/tests/dbgutil.h b/circuitpython/lib/quirc/tests/dbgutil.h new file mode 100644 index 0000000..7a5cc6a --- /dev/null +++ b/circuitpython/lib/quirc/tests/dbgutil.h @@ -0,0 +1,48 @@ +/* quirc -- QR-code recognition library + * Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#ifndef DBGUTIL_H_ +#define DBGUTIL_H_ + +#include "quirc.h" + +/* Dump decoded information on stdout. */ +void dump_data(const struct quirc_data *data); + +/* Dump a grid cell map on stdout. */ +void dump_cells(const struct quirc_code *code); + +/* Read a JPEG image into the decoder. + * + * Note that you must call quirc_end() if the function returns + * successfully (0). + */ +int load_jpeg(struct quirc *q, const char *filename); + +/* Check if a file is a PNG image. + * + * returns 1 if the given file is a PNG and 0 otherwise. + */ +int check_if_png(const char *filename); + +/* Read a PNG image into the decoder. + * + * Note that you must call quirc_end() if the function returns + * successfully (0). + */ +int load_png(struct quirc *q, const char *filename); + +#endif diff --git a/circuitpython/lib/quirc/tests/inspect.c b/circuitpython/lib/quirc/tests/inspect.c new file mode 100644 index 0000000..ce5357a --- /dev/null +++ b/circuitpython/lib/quirc/tests/inspect.c @@ -0,0 +1,264 @@ +/* quirc -- QR-code recognition library + * Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <stdio.h> +#include <string.h> +#include <SDL.h> +#include <SDL_gfxPrimitives.h> +#include "quirc_internal.h" +#include "dbgutil.h" + +static void dump_info(struct quirc *q) +{ + int count = quirc_count(q); + int i; + + printf("%d QR-codes found:\n\n", count); + for (i = 0; i < count; i++) { + struct quirc_code code; + struct quirc_data data; + quirc_decode_error_t err; + + quirc_extract(q, i, &code); + err = quirc_decode(&code, &data); + if (err == QUIRC_ERROR_DATA_ECC) { + quirc_flip(&code); + err = quirc_decode(&code, &data); + } + + dump_cells(&code); + printf("\n"); + + if (err) { + printf(" Decoding FAILED: %s\n", quirc_strerror(err)); + } else { + printf(" Decoding successful:\n"); + dump_data(&data); + } + + printf("\n"); + } +} + +static void draw_frame(SDL_Surface *screen, struct quirc *q) +{ + uint8_t *pix; + uint8_t *raw = q->image; + int x, y; + + SDL_LockSurface(screen); + pix = screen->pixels; + for (y = 0; y < q->h; y++) { + uint32_t *row = (uint32_t *)pix; + + for (x = 0; x < q->w; x++) { + uint8_t v = *(raw++); + uint32_t color = (v << 16) | (v << 8) | v; + struct quirc_region *reg = &q->regions[v]; + + switch (v) { + case QUIRC_PIXEL_WHITE: + color = 0x00ffffff; + break; + + case QUIRC_PIXEL_BLACK: + color = 0x00000000; + break; + + default: + if (reg->capstone >= 0) + color = 0x00008000; + else + color = 0x00808080; + break; + } + + *(row++) = color; + } + + pix += screen->pitch; + } + SDL_UnlockSurface(screen); +} + +static void draw_blob(SDL_Surface *screen, int x, int y) +{ + int i, j; + + for (i = -2; i <= 2; i++) + for (j = -2; j <= 2; j++) + pixelColor(screen, x + i, y + j, 0x0000ffff); +} + +static void draw_mark(SDL_Surface *screen, int x, int y) +{ + pixelColor(screen, x, y, 0xff0000ff); + pixelColor(screen, x + 1, y, 0xff0000ff); + pixelColor(screen, x - 1, y, 0xff0000ff); + pixelColor(screen, x, y + 1, 0xff0000ff); + pixelColor(screen, x, y - 1, 0xff0000ff); +} + +static void draw_capstone(SDL_Surface *screen, struct quirc *q, int index) +{ + struct quirc_capstone *cap = &q->capstones[index]; + int j; + char buf[8]; + + for (j = 0; j < 4; j++) { + struct quirc_point *p0 = &cap->corners[j]; + struct quirc_point *p1 = &cap->corners[(j + 1) % 4]; + + lineColor(screen, p0->x, p0->y, p1->x, p1->y, + 0x800080ff); + } + + draw_blob(screen, cap->corners[0].x, cap->corners[0].y); + + if (cap->qr_grid < 0) { + snprintf(buf, sizeof(buf), "?%d", index); + stringColor(screen, cap->center.x, cap->center.y, buf, + 0x000000ff); + } +} + +static void perspective_map(const double *c, + double u, double v, struct quirc_point *ret) +{ + double den = c[6]*u + c[7]*v + 1.0; + double x = (c[0]*u + c[1]*v + c[2]) / den; + double y = (c[3]*u + c[4]*v + c[5]) / den; + + ret->x = rint(x); + ret->y = rint(y); +} + +static void draw_grid(SDL_Surface *screen, struct quirc *q, int index) +{ + struct quirc_grid *qr = &q->grids[index]; + int x, y; + int i; + + for (i = 0; i < 3; i++) { + struct quirc_capstone *cap = &q->capstones[qr->caps[i]]; + char buf[16]; + + snprintf(buf, sizeof(buf), "%d.%c", index, "ABC"[i]); + stringColor(screen, cap->center.x, cap->center.y, buf, + 0x000000ff); + } + + lineColor(screen, qr->tpep[0].x, qr->tpep[0].y, + qr->tpep[1].x, qr->tpep[1].y, 0xff00ffff); + lineColor(screen, qr->tpep[1].x, qr->tpep[1].y, + qr->tpep[2].x, qr->tpep[2].y, 0xff00ffff); + + if (qr->align_region >= 0) + draw_blob(screen, qr->align.x, qr->align.y); + + for (y = 0; y < qr->grid_size; y++) { + for (x = 0; x < qr->grid_size; x++) { + double u = x + 0.5; + double v = y + 0.5; + struct quirc_point p; + + perspective_map(qr->c, u, v, &p); + draw_mark(screen, p.x, p.y); + } + } +} + +static int sdl_examine(struct quirc *q) +{ + SDL_Surface *screen; + SDL_Event ev; + + if (SDL_Init(SDL_INIT_VIDEO) < 0) { + fprintf(stderr, "couldn't init SDL: %s\n", SDL_GetError()); + return -1; + } + + screen = SDL_SetVideoMode(q->w, q->h, 32, SDL_SWSURFACE); + if (!screen) { + fprintf(stderr, "couldn't init video mode: %s\n", + SDL_GetError()); + return -1; + } + + while (SDL_WaitEvent(&ev) >= 0) { + int i; + + if (ev.type == SDL_QUIT) + break; + + if (ev.type == SDL_KEYDOWN && + ev.key.keysym.sym == 'q') + break; + + draw_frame(screen, q); + for (i = 0; i < q->num_capstones; i++) + draw_capstone(screen, q, i); + for (i = 0; i < q->num_grids; i++) + draw_grid(screen, q, i); + SDL_Flip(screen); + } + + SDL_Quit(); + return 0; +} + +int main(int argc, char **argv) +{ + struct quirc *q; + + printf("quirc inspection program\n"); + printf("Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com>\n"); + printf("Library version: %s\n", quirc_version()); + printf("\n"); + + if (argc < 2) { + fprintf(stderr, "Usage: %s <testfile.jpg|testfile.png>\n", argv[0]); + return -1; + } + + q = quirc_new(); + if (!q) { + perror("can't create quirc object"); + return -1; + } + + int status = -1; + if (check_if_png(argv[1])) { + status = load_png(q, argv[1]); + } else { + status = load_jpeg(q, argv[1]); + } + if (status < 0) { + quirc_destroy(q); + return -1; + } + + quirc_end(q); + dump_info(q); + + if (sdl_examine(q) < 0) { + quirc_destroy(q); + return -1; + } + + quirc_destroy(q); + return 0; +} diff --git a/circuitpython/lib/quirc/tests/qrtest.c b/circuitpython/lib/quirc/tests/qrtest.c new file mode 100644 index 0000000..1bb178e --- /dev/null +++ b/circuitpython/lib/quirc/tests/qrtest.c @@ -0,0 +1,309 @@ +/* quirc -- QR-code recognition library + * Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com> + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <stdio.h> +#include <errno.h> +#include <string.h> +#include <unistd.h> +#include <sys/stat.h> +#include <sys/types.h> +#include <dirent.h> +#include <ctype.h> +#include <quirc.h> +#include <jpeglib.h> +#include <setjmp.h> +#include <time.h> +#include "dbgutil.h" + +static int want_verbose = 0; +static int want_cell_dump = 0; + +#define MS(ts) (unsigned int)((ts.tv_sec * 1000) + (ts.tv_nsec / 1000000)) + +static struct quirc *decoder; + +struct result_info { + int file_count; + int id_count; + int decode_count; + + unsigned int load_time; + unsigned int identify_time; + unsigned int total_time; +}; + +static void print_result(const char *name, struct result_info *info) +{ + puts("----------------------------------------" + "---------------------------------------"); + printf("%s: %d files, %d codes, %d decoded (%d failures)", + name, info->file_count, info->id_count, info->decode_count, + (info->id_count - info->decode_count)); + if (info->id_count) + printf(", %d%% success rate", + (info->decode_count * 100 + info->id_count / 2) / + info->id_count); + printf("\n"); + printf("Total time [load: %u, identify: %u, total: %u]\n", + info->load_time, + info->identify_time, + info->total_time); + if (info->file_count) + printf("Average time [load: %u, identify: %u, total: %u]\n", + info->load_time / info->file_count, + info->identify_time / info->file_count, + info->total_time / info->file_count); +} + +static void add_result(struct result_info *sum, struct result_info *inf) +{ + sum->file_count += inf->file_count; + sum->id_count += inf->id_count; + sum->decode_count += inf->decode_count; + + sum->load_time += inf->load_time; + sum->identify_time += inf->identify_time; + sum->total_time += inf->total_time; +} + +static int scan_file(const char *path, const char *filename, + struct result_info *info) +{ + int (*loader)(struct quirc *, const char *); + int len = strlen(filename); + const char *ext; + struct timespec tp; + unsigned int start; + unsigned int total_start; + int ret; + int i; + + while (len >= 0 && filename[len] != '.') + len--; + ext = filename + len + 1; + if (strcasecmp(ext, "jpg") == 0 || strcasecmp(ext, "jpeg") == 0) + loader = load_jpeg; + else if (strcasecmp(ext, "png") == 0) + loader = load_png; + else + return 0; + + (void)clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tp); + total_start = start = MS(tp); + ret = loader(decoder, path); + (void)clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tp); + info->load_time = MS(tp) - start; + + if (ret < 0) { + fprintf(stderr, "%s: load failed\n", filename); + return -1; + } + + (void)clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tp); + start = MS(tp); + quirc_end(decoder); + (void)clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tp); + info->identify_time = MS(tp) - start; + + info->id_count = quirc_count(decoder); + for (i = 0; i < info->id_count; i++) { + struct quirc_code code; + struct quirc_data data; + + quirc_extract(decoder, i, &code); + + quirc_decode_error_t err = quirc_decode(&code, &data); + if (err == QUIRC_ERROR_DATA_ECC) { + quirc_flip(&code); + err = quirc_decode(&code, &data); + } + + if (!err) { + info->decode_count++; + } + } + + (void)clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tp); + info->total_time += MS(tp) - total_start; + + printf(" %-30s: %5u %5u %5u %5d %5d\n", filename, + info->load_time, + info->identify_time, + info->total_time, + info->id_count, info->decode_count); + + if (want_cell_dump || want_verbose) { + for (i = 0; i < info->id_count; i++) { + struct quirc_code code; + + quirc_extract(decoder, i, &code); + if (want_cell_dump) { + dump_cells(&code); + printf("\n"); + } + + if (want_verbose) { + struct quirc_data data; + quirc_decode_error_t err = quirc_decode(&code, &data); + if (err == QUIRC_ERROR_DATA_ECC) { + quirc_flip(&code); + err = quirc_decode(&code, &data); + } + + if (err) { + printf(" ERROR: %s\n\n", quirc_strerror(err)); + } else { + printf(" Decode successful:\n"); + dump_data(&data); + printf("\n"); + } + } + } + } + + info->file_count = 1; + return 1; +} + +static int test_scan(const char *path, struct result_info *info); + +static int scan_dir(const char *path, const char *filename, + struct result_info *info) +{ + DIR *d = opendir(path); + struct dirent *ent; + int count = 0; + + if (!d) { + fprintf(stderr, "%s: opendir: %s\n", path, strerror(errno)); + return -1; + } + + printf("%s:\n", path); + + while ((ent = readdir(d))) { + if (ent->d_name[0] != '.') { + char fullpath[1024]; + struct result_info sub; + + snprintf(fullpath, sizeof(fullpath), "%s/%s", + path, ent->d_name); + if (test_scan(fullpath, &sub) > 0) { + add_result(info, &sub); + count++; + } + } + } + + closedir(d); + + if (count > 1) { + print_result(filename, info); + puts(""); + } + + return count > 0; +} + +static int test_scan(const char *path, struct result_info *info) +{ + int len = strlen(path); + struct stat st; + const char *filename; + + memset(info, 0, sizeof(*info)); + + while (len >= 0 && path[len] != '/') + len--; + filename = path + len + 1; + + if (lstat(path, &st) < 0) { + fprintf(stderr, "%s: lstat: %s\n", path, strerror(errno)); + return -1; + } + + if (S_ISREG(st.st_mode)) + return scan_file(path, filename, info); + + if (S_ISDIR(st.st_mode)) + return scan_dir(path, filename, info); + + return 0; +} + +static int run_tests(int argc, char **argv) +{ + struct result_info sum; + int count = 0; + int i; + + decoder = quirc_new(); + if (!decoder) { + perror("quirc_new"); + return -1; + } + + printf(" %-30s %17s %11s\n", "", "Time (ms)", "Count"); + printf(" %-30s %5s %5s %5s %5s %5s\n", + "Filename", "Load", "ID", "Total", "ID", "Dec"); + puts("----------------------------------------" + "---------------------------------------"); + + memset(&sum, 0, sizeof(sum)); + for (i = 0; i < argc; i++) { + struct result_info info; + + if (test_scan(argv[i], &info) > 0) { + add_result(&sum, &info); + count++; + } + } + + if (count > 1) + print_result("TOTAL", &sum); + + quirc_destroy(decoder); + return 0; +} + +int main(int argc, char **argv) +{ + int opt; + + printf("quirc test program\n"); + printf("Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com>\n"); + printf("Library version: %s\n", quirc_version()); + printf("\n"); + + while ((opt = getopt(argc, argv, "vd")) >= 0) + switch (opt) { + case 'v': + want_verbose = 1; + break; + + case 'd': + want_cell_dump = 1; + break; + + case '?': + return -1; + } + + argv += optind; + argc -= optind; + + return run_tests(argc, argv);; +} |