Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Lazy -b evaluation #9

Closed
resilar opened this issue Sep 4, 2019 · 2 comments
Closed

Lazy -b evaluation #9

resilar opened this issue Sep 4, 2019 · 2 comments

Comments

@resilar
Copy link
Owner

resilar commented Sep 4, 2019

Currently -b 4: for a long input (e.g., 1GB) is handled non-lazily by allocating a huge array to store all the input bits following the 4th byte. This is stupid. Be smarter.

@resilar
Copy link
Owner Author

resilar commented Jan 10, 2024

Maybe consider simply limiting the maximum number of selected bits to w (e.g. 32 for CRC-32) for unbounded -b slices. This might work well enough in practice.

resilar added a commit that referenced this issue Mar 30, 2024
previously unbounded slices such as `-b 4:` selected every input message
bit after the 4th byte. for long input messages (think gigabytes) this
resulted in crchack allocating crazy amounts of memory for input.bits[]
array containing an element for each selected bit, ultimately freezing
and/or aborting the entire program due to "out of memory" error.

the commit addresses the issue by limiting the maximum number of bits
selected by a single -b command-line switch to w where w is the register
width of the specified CRC function. rudimentary testing shows that this
does not introduce new failures when forging CRC checksums, probably
because w mutable bits is practically always enough to obtain the target
checksum (however, i would not be surprised if there are some edge cases
where this does not hold - but let's address that separately if that
problem ever comes up).

lastly, this commit also implements support for negative zero offsets
for command-line offset switches (-o/-O). before `-o -0` was identical
to `-o 0`, whereas the expected behavior would be `-O 0`, i.e., offset
pointing at the end of the input message. yes, it'd have made sense to
split this change into another commit, but i'm feeling lazy so fuck it.
@resilar
Copy link
Owner Author

resilar commented Mar 30, 2024

59e3e3d commit limits the maximum number of bits selected by a single -b slice to w, i.e., the CRC polynomial (register) width. Rudimentary testing shows that this approach works well in practice and does not seem to make forging fail in situations where it previously succeeded with the old code. Note that this is not obvious because the w bits chosen by an unbounded -b are not necessarily contiguous if the step parameter of the slice is not equal to 1 bit, so even if -o 420 which selects w contiguous bits is guaranteed to make forging successful, the same may not hold for an -b slice that also selects w bits because they may be non-contiguous.

I think we should consider deprecating offset switches -o/-O at some point because -b switches are now expressive and user-friendly enough to offer the same functionality: -o 42 and -b 42: are essentially identical. Similarly, -O 42 and -b -42: are equivalent to each other. The only disadvantage of -b command-line options is that appending to the input is unsupported when forging CRC checksums, whereas -o and -O do support appending to the end of the input message. However, the current append mechanism should probably be rewritten anyway to support prepending also (as discussed in issue #11). I'm creating a new issue regarding the deprecation of -o/-O in favor of -b.

Closing this issue, at least until it turns out there are some cases where the previous behavior forged some messages correctly while the new "select at most w bits" approach fails.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant