JuliaImages / QRCoders.jl

Creating QR Codes within Julia
https://juliaimages.org/QRCoders.jl/
MIT License
67 stars 11 forks source link

Improve Polynomial operation #27

Closed RexWzh closed 1 year ago

RexWzh commented 1 year ago

Improve Polynomial operation

Benchmark results

using BenchmarkTools
using QRCoders
using QRCode.Polynomial: Poly as OriPoly

randpoly(n::Int) = Poly([rand(0:255, n-1)..., rand(1:255)])
f1 = randpoly(100);
f2 = OriPoly(f1.coeff);
@btime f1 * f1;
@btime f2 * f2;

# 9.219 μs (2 allocations: 1.78 KiB)
# 325.375 μs (501 allocations: 555.11 KiB)

For the encoding part, polynomial operation is used only in geterrorcorrection.

exportqrcode =1> qrcode =1> encodemessage
=at most 59> getecblock =1> geterrorcorrection

So it decreases little of the efficiency comparing to the other operations.

Current result msg cost
"Hello world!" 129.871 μs (270 allocations: 19.34 KiB)
"0123456789" ^ 30 1.223 ms (1068 allocations: 96.20 KiB)
"HELLO WORLD" ^ 30 2.036 ms (1655 allocations: 157.61 KiB)
"HELLO WORLD" ^ 190 11.962 ms (8930 allocations: 882.53 KiB)
Previous one input string cost
"Hello world!" 142.909 μs (370 allocations: 32.23 KiB)
"0123456789" ^ 30 1.454 ms (1982 allocations: 291.95 KiB)
"HELLO WORLD" ^ 30 2.495 ms (3200 allocations: 562.52 KiB)
"HELLO WORLD" ^ 190 14.310 ms (17825 allocations: 3.01 MiB)

However, Efficiency of polynomial operations are important in QRDecoders.jl, since they are used frequently.


Original implement:

function *(a::Poly, b::Poly)::Poly
    return sum([ c * (a << (p - 1)) for (p, c) in enumerate(b.coeff)])
end

Here c * Poly, a << Int and Poly + Poly will create new polynomials.

New one:

function *(a::Poly, b::Poly)::Poly
    prodpoly = Poly(zeros(Int, length(a) + length(b) - 1))
    @inbounds for (i, c1) in enumerate(a.coeff), (j, c2) in enumerate(b.coeff)
        prodpoly.coeff[i + j - 1] ⊻= mult(c2, c1) # column first
    end
    return prodpoly
end
codecov[bot] commented 1 year ago

Codecov Report

Base: 100.00% // Head: 99.73% // Decreases project coverage by -0.26% :warning:

Coverage data is based on head (5885b38) compared to base (c55b759). Patch coverage: 100.00% of modified lines in pull request are covered.

:exclamation: Current head 5885b38 differs from pull request most recent head 5d53b70. Consider uploading reports for the commit 5d53b70 to get more accurate results

Additional details and impacted files ```diff @@ Coverage Diff @@ ## master #27 +/- ## =========================================== - Coverage 100.00% 99.73% -0.27% =========================================== Files 5 5 Lines 361 372 +11 =========================================== + Hits 361 371 +10 - Misses 0 1 +1 ``` | [Impacted Files](https://codecov.io/gh/JuliaImages/QRCoders.jl/pull/27?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=JuliaImages) | Coverage Δ | | |---|---|---| | [src/tables.jl](https://codecov.io/gh/JuliaImages/QRCoders.jl/pull/27/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=JuliaImages#diff-c3JjL3RhYmxlcy5qbA==) | `100.00% <ø> (ø)` | | | [src/encode.jl](https://codecov.io/gh/JuliaImages/QRCoders.jl/pull/27/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=JuliaImages#diff-c3JjL2VuY29kZS5qbA==) | `100.00% <100.00%> (ø)` | | | [src/errorcorrection.jl](https://codecov.io/gh/JuliaImages/QRCoders.jl/pull/27/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=JuliaImages#diff-c3JjL2Vycm9yY29ycmVjdGlvbi5qbA==) | `98.78% <100.00%> (-1.22%)` | :arrow_down: | Help us with your feedback. Take ten seconds to tell us [how you rate us](https://about.codecov.io/nps?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=JuliaImages). Have a feature suggestion? [Share it here.](https://app.codecov.io/gh/feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=JuliaImages)

:umbrella: View full report at Codecov.
:loudspeaker: Do you have feedback about the report comment? Let us know in this issue.