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.

Sign up for GitHub

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

Jump to bottom

change huffman::table to always be canonical #90

Closed
garymm opened this issue Sep 26, 2023 · 1 comment · Fixed by #101
Closed

change huffman::table to always be canonical #90

garymm opened this issue Sep 26, 2023 · 1 comment · Fixed by #101

Comments

@garymm
Copy link
Owner

garymm commented Sep 26, 2023

And optimize table::find to take advantage of that.
oliverlee added a commit that referenced this issue Oct 5, 2023
@oliverlee
use random access indexing in huffman::table::find
c602968 
All DEFLATE canonical codes of a given bitsize are lexicographically
consecutive values in the same order as the symbols they represent. As
a result, the skip field for the first code of a given bitsize can be
used to determine if an input code exists in the table in constant time.

This commit replaces the linear time search of all codes of a given
bitsize in huffman::table::find. Instead, the find method does the
following:
* if the input code bitsize is greater than the iterator code bitsize,
  advance the iterator by the iterator skip field
* if the input code bitsize is less than the iterator code bitsize,
  return the iterator as an error
* if the input code bitsize is equal to the iterator code bitsize:
  - determine the distance from the iterator code value to the input
    code value. If it is less than the iterator skip field, advance the
    iterator by the calculated distance and return the iterator as a
    success; otherwise
  - advance the iterator by the iterator skip field and continue

resolves #90

Change-Id: Ic736c4d2e0150e53bd7bf1870104462294368a5c
@oliverlee oliverlee mentioned this issue Oct 5, 2023
Merged
oliverlee added a commit that referenced this issue Oct 7, 2023
@oliverlee
use random access indexing in huffman::table::find
a4795ec 
All DEFLATE canonical codes of a given bitsize are lexicographically
consecutive values in the same order as the symbols they represent. As
a result, the skip field for the first code of a given bitsize can be
used to determine if an input code exists in the table in constant time.

This commit replaces the linear time search of all codes of a given
bitsize in huffman::table::find. Instead, the find method does the
following:
* if the input code bitsize is greater than the iterator code bitsize,
  advance the iterator by the iterator skip field
* if the input code bitsize is less than the iterator code bitsize,
  return the iterator as an error
* if the input code bitsize is equal to the iterator code bitsize:
  - determine the distance from the iterator code value to the input
    code value. If it is less than the iterator skip field, advance the
    iterator by the calculated distance and return the iterator as a
    success; otherwise
  - advance the iterator by the iterator skip field and continue

resolves #90

Change-Id: Ic736c4d2e0150e53bd7bf1870104462294368a5c
oliverlee added a commit that referenced this issue Oct 7, 2023
@oliverlee
use random access indexing in huffman::table::find
2fb547f 
All DEFLATE canonical codes of a given bitsize are lexicographically
consecutive values in the same order as the symbols they represent. As
a result, the skip field for the first code of a given bitsize can be
used to determine if an input code exists in the table in constant time.

This commit replaces the linear time search of all codes of a given
bitsize in huffman::table::find. Instead, the find method does the
following:
* if the input code bitsize is greater than the iterator code bitsize,
  advance the iterator by the iterator skip field
* if the input code bitsize is less than the iterator code bitsize,
  return the iterator as an error
* if the input code bitsize is equal to the iterator code bitsize:
  - determine the distance from the iterator code value to the input
    code value. If it is less than the iterator skip field, advance the
    iterator by the calculated distance and return the iterator as a
    success; otherwise
  - advance the iterator by the iterator skip field and continue

resolves #90

Change-Id: Ic736c4d2e0150e53bd7bf1870104462294368a5c
garymm pushed a commit that referenced this issue Oct 13, 2023
@oliverlee @garymm
use random access indexing in huffman::table::find
f041213 
All DEFLATE canonical codes of a given bitsize are lexicographically
consecutive values in the same order as the symbols they represent. As
a result, the skip field for the first code of a given bitsize can be
used to determine if an input code exists in the table in constant time.

This commit replaces the linear time search of all codes of a given
bitsize in huffman::table::find. Instead, the find method does the
following:
* if the input code bitsize is greater than the iterator code bitsize,
  advance the iterator by the iterator skip field
* if the input code bitsize is less than the iterator code bitsize,
  return the iterator as an error
* if the input code bitsize is equal to the iterator code bitsize:
  - determine the distance from the iterator code value to the input
    code value. If it is less than the iterator skip field, advance the
    iterator by the calculated distance and return the iterator as a
    success; otherwise
  - advance the iterator by the iterator skip field and continue

resolves #90

Change-Id: Ic736c4d2e0150e53bd7bf1870104462294368a5c
@garymm
Copy link
Owner Author

garymm commented Dec 12, 2023

Fixed by #100

@garymm garymm closed this as completed Dec 12, 2023
oliverlee added a commit that referenced this issue Jan 6, 2024
@oliverlee
use random access indexing in huffman::table::find
e343fbf 
All DEFLATE canonical codes of a given bitsize are lexicographically
consecutive values in the same order as the symbols they represent. As
a result, the skip field for the first code of a given bitsize can be
used to determine if an input code exists in the table in constant time.

This commit replaces the linear time search of all codes of a given
bitsize in huffman::table::find. Instead, the find method does the
following:
* if the input code bitsize is greater than the iterator code bitsize,
  advance the iterator by the iterator skip field
* if the input code bitsize is less than the iterator code bitsize,
  return the iterator as an error
* if the input code bitsize is equal to the iterator code bitsize:
  - determine the distance from the iterator code value to the input
    code value. If it is less than the iterator skip field, advance the
    iterator by the calculated distance and return the iterator as a
    success; otherwise
  - advance the iterator by the iterator skip field and continue

resolves #90

Change-Id: Ic736c4d2e0150e53bd7bf1870104462294368a5c
oliverlee added a commit that referenced this issue Jan 6, 2024
@oliverlee
use random access indexing in huffman::table::find (#101)
b4f1ad9 
All DEFLATE canonical codes of a given bitsize are lexicographically
consecutive values in the same order as the symbols they represent. As
a result, the skip field for the first code of a given bitsize can be
used to determine if an input code exists in the table in constant time.

This commit replaces the linear time search of all codes of a given
bitsize in huffman::table::find. Instead, the find method does the
following:
* if the input code bitsize is greater than the iterator code bitsize,
  advance the iterator by the iterator skip field
* if the input code bitsize is less than the iterator code bitsize,
  return the iterator as an error
* if the input code bitsize is equal to the iterator code bitsize:
  - determine the distance from the iterator code value to the input
    code value. If it is less than the iterator skip field, advance the
    iterator by the calculated distance and return the iterator as a
    success; otherwise
  - advance the iterator by the iterator skip field and continue

resolves #90

Change-Id: Ic736c4d2e0150e53bd7bf1870104462294368a5c
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

use random access indexing in huffman::table::find garymm/starflate
1 participant
@garymm