LZ0 - Asymmetric LZ compressor with zero-malloc decoder
Show HN: LZ0 -An asymmetric LZ compressor with ultra minimal, 0-alloc decoder
LZ0은 압축 해제기의 극단적인 단순함에 초점을 맞춘 실험적인 무손실 압축 포맷이자 C 구현입니다. 인코더가 더 많은 계산을 담당하는 대신, 디코더는 동적 메모리 할당 없이 단 몇 개의 스택 레지스터만으로 동작하며 초당 수백 MB의 속도로 압축을 해제합니다. 작은 바이너리부터 수 MB의 구조화된 데이터까지 빠르게 처리할 수 있어, 부트로더, 마이크로컨트롤러, 커널 드라이버 같은 자원 제약 환경에 이상적입니다. ZX0와 유사한 압축률을 유지하면서도 인코딩 속도를 크게 개선했고, x86-64, ARM64, RISC-V용 초소형 어셈블리 디코더도 제공합니다.
복잡성을 디코더에서 인코더로 옮기세요. LZ0는 압축 해제 루틴을 극도로 단순화하여 메모리 할당 없이도 빠르게 동작합니다.
- nellacross
LZ4와의 더 깊은 비교를 보고 싶습니다. LZ4 스타일 디코더는 최소한으로 만들 수 있고, LZ4HC를 사용하면 압축 해제 속도를 희생하지 않으면서 더 나은 밀도를 얻을 수 있습니다.
- aidenn0
lz4hc -9와의 벤치마크를 보는 것이 좋겠습니다. 압축 속도와 압축 해제 속도 모두에서 가장 가까운 경쟁자이기 때문입니다.
- seb3773
저는 LZ0를 만들었습니다. 이는 압축 해제 리소스가 매우 제한된 환경(부트로더, 마이크로컨트롤러, 임베디드 에셋 로딩)이나 디코더 단순성이 가장 중요한 곳을 대상으로 하는 비대칭 LZ 압축기입니다.
저는 Einar Saukas의 ZX0 같은 마이크로 디코더를 항상 동경해 왔습니다. 동적 할당 제로, 스크래치 RAM 없음, 그리고 몇 개의 명령어에 들어갈 만큼 작습니다. 전통적인 최적 파서의 문제는 파일이 수백 킬로바이트를 넘으면 종종 O(N^2)으로 확장되어 수십 초 또는 수 분이 걸린다는 점입니다. 저는 수 메가바이트 파일을 밀리초 단위로 압축하면서도 동일한 디코더 풋프린트를 유지하기 위해 LZ0를 작성했습니다.
위치(압축률 대 속도): - 압축 밀도: LZ4/Snappy를 능가하며 zlib/Deflate 및 완전 탐색 ZX0의 1–3% 이내에 머뭅니다. - 압축 해제 속도: 이식성 C의 경우 200–350 MB/s, 컴팩트 ASM의 경우 250–700 MB/s, 벡터 ASM의 경우 520–1,330 MB/s입니다. 이는 Deflate보다 최대 10배 빠르면서 힙 메모리나 상태 테이블이 전혀 필요 없습니다. - 압축 처리량: 일반적인 1 MB 입력에서 ~1.3–1.6초.
인코더가 O(N^2) 장벽을 피하는 방법(H2C8 파이프라인): - 다중 계층 매치 찾기: 로컬 매치를 위한 이중 레벨 해시 체인과 깊고 장거리 매치를 위한 O(N) SA-IS 접미사 배열을 결합합니다. - 희소 DP 파싱: 그래프의 모든 간선을 평가하는 대신 Elias 감마 비트 비용을 수학적 플래토로 그룹화하여 중복 검색을 건너뜁니다.
저장소에는 세 가지 0-할당 디코더 구현이 포함되어 있습니다: 1. 이식성 C(`lz0dec_min.c`): ~75줄의 프리스탠딩 C로 […]