Add quirc_end_with_workarea()

[yamt]

• add a new variant of quirc_end() to allow users to specify the working memory for the flood filling logic
• motivation: the dynamic stack usage with recursion is not easy to deal with. (for me) eg. malloc/free is easier than launching a temporary thread with a large stack.
• implementation:
  • make flood filling logic iterative. (vs recursive) i basically tried one-to-one conversions here to avoid mistakes. probably it has a room for later improvements.
  • passes around the user-specified working memory for flood fill
• possible downsides:
  • might have a negative impact on architectures with fast stack. eg. something with register-window
  • might have a negative impact on demand-paged stack

[yamt]

btw, i'm not quite happy with the name quirc_end_with_workarea. suggestions are welcome.

[kaworu]

Hello @yamt and thank you for the contribution! I'll defer to @dlbeer about the flood-fill related changes and possible impact on embedded.

[dlbeer]

How big does a workarea need to be for the library to behave well on typical images? I'm guessing it's of the order of a thousand-ish entries?

I'm very much in favour of removing the recursion, but I wonder if the workarea could just be allocated with a static fixed (or #define'd) size in struct quirc? We already have a static buffer for grid decoding, and I'm guessing this wouldn't add significantly to the size.

[yamt]

How big does a workarea need to be for the library to behave well on typical images? I'm guessing it's of the order of a thousand-ish entries?

i was assuming that FLOOD_FILL_MAX_DEPTH was the value for the typical images. wasn't it?

I'm very much in favour of removing the recursion, but I wonder if the workarea could just be allocated with a static fixed (or #define'd) size in struct quirc? We already have a static buffer for grid decoding, and I'm guessing this wouldn't add significantly to the size.

depends on the typical size, it might make sense.

[dlbeer]

FLOOD_FILL_MAX_DEPTH is probably an overestimate, and was there to prevent stack overflow with the recursive flood-fill. I suspect you can probably get away with less, since the flood-fill really only needs to work well enough to distinguish features like rings and capstones. Happy for you to experiment with this and pick out what you think is a reasonable value.

[yamt]

FLOOD_FILL_MAX_DEPTH is probably an overestimate, and was there to prevent stack overflow with the recursive flood-fill.

ok.

I suspect you can probably get away with less, since the flood-fill really only needs to work well enough to distinguish features like rings and capstones. Happy for you to experiment with this and pick out what you think is a reasonable value.

some of my colleagues might have some experiment results about this. let me ask them.

[yamt]

I suspect you can probably get away with less, since the flood-fill really only needs to work well enough to distinguish features like rings and capstones. Happy for you to experiment with this and pick out what you think is a reasonable value.

some of my colleagues might have some experiment results about this. let me ask them.

unfortunately, they don't seem to have much info to share.

[yamt]

@dlbeer

reading at the code, i think that the max depth should be something like (image_height_in_pixels / 3 * 2).

• rings are the most stack consuming regions to fill.
• they consumes the stack the most when they are rotated by about 45 degree. (the depth would be about 2 * height)
• the max height of rings is about 1/3 of the image height.

as it's a proportion to the image resolution, i guess there's no one-size-fit-all value of the max depth. how do you think?

[yamt]

reading at the code, i think that the max depth should be something like (image_height_in_pixels / 3 * 2).

i did quick experiments around this value and it seems working as i expected. (in my case image_height_in_pixels=720)

i guess it makes sense to make quirc_resize() allocate the buffer with this size automatically using malloc(). how do you think?

[yamt]

i guess it makes sense to make quirc_resize() allocate the buffer with this size automatically using malloc().

i submitted an alternative version which do this. https://github.com/dlbeer/quirc/pull/100

[yamt]

i haven't noticed any issues with the alternative (https://github.com/dlbeer/quirc/pull/100) so far. let me close this one.