7 ms·

Generating a QR code with only ARM Assembly

85 points by barrettotte 5y ago

jdblair 5y ago
Bravo!
amelius 5y ago
OT. Does anyone know of a good open source library to read "Data Matrix" 2d barcodes? The ones I found are either broken or extremely slow. The frustrating part is that there seem to be many mobile phone apps which can do it just fine, but I want to run this in my own code on my desktop machine, so each barcode can trigger an appropriate action.
- zwieback 5y ago
  The only one I've used is https://github.com/zxing/zxing https://github.com/zxing/zxing, but it was a long time ago. Seemed to work ok for DataMatrix.
  - gregsadetsky 5y ago
    zxing has an online decoder -- https://zxing.org/w/decode.jspx https://zxing.org/w/decode.jspx -- but I've seen it fail so often that I'm wondering whether it's very "strict" / doesn't account for image distortion that much? Or does the web site use hardcoded settings that are more tweakable in the library? Huh, interesting -- zxing is in "Maintenance Mode Only": https://github.com/zxing/zxing https://github.com/zxing/zxing I'd be suuuuper interested to know: what's the state of the art in terms of QR decoding, both in terms of decoding speed, amenability to various image distortions, and (which I've always dreamed of) the ability to partially decode a QR code, even if the error correction fails for some parts of it, or even totally? i.e. a very very verbose debugging/decoding mode?
  - ianlevesque 5y ago
    If you just want effective and free and don’t care about open, Google’s is the best https://developers.google.com/ml-kit/vision/barcode-scanning https://developers.google.com/ml-kit/vision/barcode-scanning Also depending on your application you could buy a hardware scanner like https://www.zebra.com/us/en/products/scanners/fixed-mount-scanners/ds457.html https://www.zebra.com/us/en/products/scanners/fixed-mount-sc... for cheap secondhand since they are all over retail. The protocol can be as simple as it “types” the barcode over USB HID like a keyboard, or there are more specialized modes.
    - amelius 5y ago
      Google's barcode kit seems to be available only for Android and iOS.
  - pabs3 5y ago
    The zxing C++ port worked for me recently: https://github.com/nu-book/zxing-cpp/ https://github.com/nu-book/zxing-cpp/
- dmitrygr 5y ago
  The spec is quite clear (i was able to implement creating datamatrix codes of all sizes/shaped from the spec in C in a day). Take a look at it. It also covers how to decode them. You might be able to write it yourself and learn a lot in the process. It goes into great depth on suggested methods to decode. See section 9 "Reference decode algorithm for Data Matrix" in ISO/IEC 16022 second edition 2006-09-15, which you'll need to BUY... I've uploaded for you to view here: https://mega.nz/file/ctQCxDaQ#Y7-XyMeR2e8nJQ79cJfWKmlfwxPm2Q8Een1dY9CrApA https://mega.nz/file/ctQCxDaQ#Y7-XyMeR2e8nJQ79cJfWKmlfwxPm2Q... Because, fuck ISO for paywalling knowledge!
  - codetrotter 5y ago
    Hos do you correct for angles around the axes x, y and z? That’s the hard part I imagine
    - deleted 5y ago
      [deleted]
    - dmitrygr 5y ago
      I updated the comment you replied to with more info :)
    - wizzwizz4 5y ago
      I found another paper: https://www.hindawi.com/journals/mpe/2013/848276/ https://www.hindawi.com/journals/mpe/2013/848276/
      - gregsadetsky 5y ago
        And here's a Matlab implementation based on that paper: https://github.com/lapauwThomas/QR_reader https://github.com/lapauwThomas/QR_reader Would be curious to see how it performs.
  - nayuki 5y ago
    Thanks, this is going to be a fun read. =)
- cameldrv 5y ago
  I wasn't able to find one for an important project and we ended up having to go with a commercial library. The open source ones were very unreliable.
  - gregsadetsky 5y ago
    Would you mind sharing which one? Did you look at a few / are there good comparison articles?
    - jiehong 5y ago
      No OP, but I'm aware of a few: - scandit: https://www.scandit.com/developers/ https://www.scandit.com/developers/ - cognex: https://cmbdn.cognex.com/ https://cmbdn.cognex.com/ - aspose: https://products.aspose.com/barcode/ https://products.aspose.com/barcode/ In open source, I heard of libdmtx[0], but not much happens on it these days. I also saw html5-qrcode[1] [0]: https://github.com/dmtx https://github.com/dmtx [1]: https://github.com/mebjas/html5-qrcode https://github.com/mebjas/html5-qrcode, which directly depends on a port of zxing to javascript.
      - cameldrv 5y ago
        There are a lot more QR code libraries available, and while they're conceptually very similar, the open source DataMatrix libraries are much less developed and are far less reliable.
      - gregsadetsky 5y ago
        Fascinating, thanks a lot for these. Scandit and Cognex have iOS apps, and Aspose has a web recognizer demo. I tried all three with a 2D QR code (my vax card!) from which I truncated ~2-3 bit-"rows" from the bottom. None of the apps/site detected the code. This is truly not a thorough test -- the 2D rows may be more information-dense than I think i.e. they are not recoverable using the built-in error correction (basically I'm removing too much information -- the equivalent of a long/deep scratch on a CD). -- I'm just trying to get an intuitive sense of how much damage a QR code can sustain and ... I guess if there's such a thing as QR code forensics (there must be...??) for decoding partial codes versus not detecting "anything". Thanks again for the links. Super interesting space
- lloydatkinson 5y ago
  This is the third request for datamatrix barcodes I've seen on HN, Twitter, and Reddit today. What's going on?
  - amelius 5y ago
    I don't know about others, but I want to read Digikey barcodes. They are in data-matrix format.
rebane2001 5y ago
On a similar note, I've been working on a QR code generator in Minecraft using redstone (the in-game equivalent of circuits), it has both been rather interesting and very painful to create. Definitely a great way to gain experience. I'll probably finish the project sometime this week.
- barrettotte 5y ago
  Oh man I always wanted to build some insane things with redstone, but never got around to diving in. I have a little 4-bit architecture I'm working on so one day I can implement it in Minecraft and/or Satisfactory. I hope to see your creation sometime, that sounds awesome
  - nimvlaj30 5y ago
    Apparently it is possible to create QR codes on Factorio's minimap as well. I wonder if it could be automated using the in-game construction bots. [Example](https://www.reddit.com/r/factorio/comments/gqfi33/you_can_make_qr_codes_in_factorio_d/ https://www.reddit.com/r/factorio/comments/gqfi33/you_can_ma...)
userbinator 5y ago
you should obviously never use assembly for this type of project/application. ...unless you're working in certain types of embedded development, where rewriting code in Asm to save going to the next larger size of device is a semi-common occurrence. I'm not really familiar with ARM Asm so I can't easily point out optimisation opportunities like I can with x86, but would like to see a size comparison with a stripped-down C implementation (of similar capability) put through a compiler.
- haolez 5y ago
  Wouldn't -Os optimize for size better than hand-crafted ASM? Genuine question.
  - deleted 5y ago
    [deleted]
  - userbinator 5y ago
    My experience is mostly with x86, where the answer is a definitive "no"; for ARM, my guess is "likely no" --- it's a RISC, so instruction selection isn't as critical, and all instructions are fixed-width so again there isn't as much flexibility in instruction selection (e.g. in x86 a "xor reg, reg" is the canonical way to zero a register, and explicit loading with a constant 0 is very much discouraged and a few bytes bigger, even compilers know about that now.) That said, I've also seen compilers do ridiculous stupid things which no human ever would.
  - MaxLeiter 5y ago
    Cant speak much for x86, but for many older / less common architectures (I can speak for z80) the compilers aren’t as advanced or are missing extensive optimizations.
fmakunbound 5y ago
Every line in the code base is commented

85 points by barrettotte 5y ago

Bravo!

OT. Does anyone know of a good open source library to read "Data Matrix" 2d barcodes? The ones I found are either broken or extremely slow. The frustrating part is that there seem to be many mobile phone apps which can do it just fine, but I want to run this in my own code on my desktop machine, so each barcode can trigger an appropriate action.

zwieback 5y ago
The only one I've used is https://github.com/zxing/zxing https://github.com/zxing/zxing, but it was a long time ago. Seemed to work ok for DataMatrix.
- gregsadetsky 5y ago
  zxing has an online decoder -- https://zxing.org/w/decode.jspx https://zxing.org/w/decode.jspx -- but I've seen it fail so often that I'm wondering whether it's very "strict" / doesn't account for image distortion that much? Or does the web site use hardcoded settings that are more tweakable in the library? Huh, interesting -- zxing is in "Maintenance Mode Only": https://github.com/zxing/zxing https://github.com/zxing/zxing I'd be suuuuper interested to know: what's the state of the art in terms of QR decoding, both in terms of decoding speed, amenability to various image distortions, and (which I've always dreamed of) the ability to partially decode a QR code, even if the error correction fails for some parts of it, or even totally? i.e. a very very verbose debugging/decoding mode?
- ianlevesque 5y ago
  If you just want effective and free and don’t care about open, Google’s is the best https://developers.google.com/ml-kit/vision/barcode-scanning https://developers.google.com/ml-kit/vision/barcode-scanning Also depending on your application you could buy a hardware scanner like https://www.zebra.com/us/en/products/scanners/fixed-mount-scanners/ds457.html https://www.zebra.com/us/en/products/scanners/fixed-mount-sc... for cheap secondhand since they are all over retail. The protocol can be as simple as it “types” the barcode over USB HID like a keyboard, or there are more specialized modes.
  - amelius 5y ago
    Google's barcode kit seems to be available only for Android and iOS.
- pabs3 5y ago
  The zxing C++ port worked for me recently: https://github.com/nu-book/zxing-cpp/ https://github.com/nu-book/zxing-cpp/
dmitrygr 5y ago
The spec is quite clear (i was able to implement creating datamatrix codes of all sizes/shaped from the spec in C in a day). Take a look at it. It also covers how to decode them. You might be able to write it yourself and learn a lot in the process. It goes into great depth on suggested methods to decode. See section 9 "Reference decode algorithm for Data Matrix" in ISO/IEC 16022 second edition 2006-09-15, which you'll need to BUY... I've uploaded for you to view here: https://mega.nz/file/ctQCxDaQ#Y7-XyMeR2e8nJQ79cJfWKmlfwxPm2Q8Een1dY9CrApA https://mega.nz/file/ctQCxDaQ#Y7-XyMeR2e8nJQ79cJfWKmlfwxPm2Q... Because, fuck ISO for paywalling knowledge!
- codetrotter 5y ago
  Hos do you correct for angles around the axes x, y and z? That’s the hard part I imagine
  - deleted 5y ago
    [deleted]
  - dmitrygr 5y ago
    I updated the comment you replied to with more info :)
  - wizzwizz4 5y ago
    I found another paper: https://www.hindawi.com/journals/mpe/2013/848276/ https://www.hindawi.com/journals/mpe/2013/848276/
    - gregsadetsky 5y ago
      And here's a Matlab implementation based on that paper: https://github.com/lapauwThomas/QR_reader https://github.com/lapauwThomas/QR_reader Would be curious to see how it performs.
- nayuki 5y ago
  Thanks, this is going to be a fun read. =)
cameldrv 5y ago
I wasn't able to find one for an important project and we ended up having to go with a commercial library. The open source ones were very unreliable.
- gregsadetsky 5y ago
  Would you mind sharing which one? Did you look at a few / are there good comparison articles?
  - jiehong 5y ago
    No OP, but I'm aware of a few: - scandit: https://www.scandit.com/developers/ https://www.scandit.com/developers/ - cognex: https://cmbdn.cognex.com/ https://cmbdn.cognex.com/ - aspose: https://products.aspose.com/barcode/ https://products.aspose.com/barcode/ In open source, I heard of libdmtx[0], but not much happens on it these days. I also saw html5-qrcode[1] [0]: https://github.com/dmtx https://github.com/dmtx [1]: https://github.com/mebjas/html5-qrcode https://github.com/mebjas/html5-qrcode, which directly depends on a port of zxing to javascript.
    - cameldrv 5y ago
      There are a lot more QR code libraries available, and while they're conceptually very similar, the open source DataMatrix libraries are much less developed and are far less reliable.
    - gregsadetsky 5y ago
      Fascinating, thanks a lot for these. Scandit and Cognex have iOS apps, and Aspose has a web recognizer demo. I tried all three with a 2D QR code (my vax card!) from which I truncated ~2-3 bit-"rows" from the bottom. None of the apps/site detected the code. This is truly not a thorough test -- the 2D rows may be more information-dense than I think i.e. they are not recoverable using the built-in error correction (basically I'm removing too much information -- the equivalent of a long/deep scratch on a CD). -- I'm just trying to get an intuitive sense of how much damage a QR code can sustain and ... I guess if there's such a thing as QR code forensics (there must be...??) for decoding partial codes versus not detecting "anything". Thanks again for the links. Super interesting space
lloydatkinson 5y ago
This is the third request for datamatrix barcodes I've seen on HN, Twitter, and Reddit today. What's going on?
- amelius 5y ago
  I don't know about others, but I want to read Digikey barcodes. They are in data-matrix format.

rebane2001 5y ago

On a similar note, I've been working on a QR code generator in Minecraft using redstone (the in-game equivalent of circuits), it has both been rather interesting and very painful to create. Definitely a great way to gain experience. I'll probably finish the project sometime this week.

barrettotte 5y ago
Oh man I always wanted to build some insane things with redstone, but never got around to diving in. I have a little 4-bit architecture I'm working on so one day I can implement it in Minecraft and/or Satisfactory. I hope to see your creation sometime, that sounds awesome
- nimvlaj30 5y ago
  Apparently it is possible to create QR codes on Factorio's minimap as well. I wonder if it could be automated using the in-game construction bots. [Example](https://www.reddit.com/r/factorio/comments/gqfi33/you_can_make_qr_codes_in_factorio_d/ https://www.reddit.com/r/factorio/comments/gqfi33/you_can_ma...)

userbinator 5y ago

you should obviously never use assembly for this type of project/application. ...unless you're working in certain types of embedded development, where rewriting code in Asm to save going to the next larger size of device is a semi-common occurrence. I'm not really familiar with ARM Asm so I can't easily point out optimisation opportunities like I can with x86, but would like to see a size comparison with a stripped-down C implementation (of similar capability) put through a compiler.

haolez 5y ago
Wouldn't -Os optimize for size better than hand-crafted ASM? Genuine question.
- deleted 5y ago
  [deleted]
- userbinator 5y ago
  My experience is mostly with x86, where the answer is a definitive "no"; for ARM, my guess is "likely no" --- it's a RISC, so instruction selection isn't as critical, and all instructions are fixed-width so again there isn't as much flexibility in instruction selection (e.g. in x86 a "xor reg, reg" is the canonical way to zero a register, and explicit loading with a constant 0 is very much discouraged and a few bytes bigger, even compilers know about that now.) That said, I've also seen compilers do ridiculous stupid things which no human ever would.
- MaxLeiter 5y ago
  Cant speak much for x86, but for many older / less common architectures (I can speak for z80) the compilers aren’t as advanced or are missing extensive optimizations.

fmakunbound 5y ago

Every line in the code base is commented