russell@unturf.com
8a3fc56b23
libjpeg-turbo-0001: rdcolmap.c add_map_entry() O(P*C) linear color dedup. For each pixel in a PPM colormap file, a linear scan checks the palette (up to 256 entries). With large images (JPEG_MAX_DIMENSION=65500) and a saturated palette, cost reaches O(W*H*256). Fix: open-addressing hash set resets once per _read_color_map() call, giving O(1) average per pixel. Measured 128-131x speedup. 7/7 unit tests PASS. libwebp: CLEAN on all 5 MOADs. GetColorPalette uses open-addressing hash, backward references use hash chains, palette sort O(N^2) bounded to N<=256 once per image, DSP init uses mutex-protected lazy initialization.
61 lines
2.5 KiB
Markdown
61 lines
2.5 KiB
Markdown
# libwebp — 5-MOAD Scan Result: CLEAN
|
|
|
|
## Target
|
|
|
|
libwebp (WebP codec, C), commit depth=1 from github.com/webmproject/libwebp
|
|
|
|
## MOAD-0001 — CWE-407 CLEAN
|
|
|
|
All hot-path membership checks use hash-based data structures:
|
|
|
|
- **GetColorPalette() (`src/utils/palette.c`)**: open-addressing hash table
|
|
(`COLOR_HASH_SIZE = MAX_PALETTE_SIZE * 4` = 1024 slots) with linear probing.
|
|
No linear scan per pixel.
|
|
|
|
- **SearchColorNoIdx() (`src/utils/palette.c`)**: binary search over a
|
|
pre-sorted palette array. O(log N) per lookup.
|
|
|
|
- **PrepareMapToPalette()**: `qsort` + binary search. No linear scan.
|
|
|
|
- **VP8LHashChain (`src/enc/backward_references_enc.c`)**: hash chain for
|
|
LZ77 backward reference matching. Inner `for` loop follows pre-built hash
|
|
chain links (bounded by `iter_max`), not a flat array scan.
|
|
|
|
- **Huffman tree build (`src/utils/huffman_encode_utils.c`)**: uses insertion
|
|
sort inside the tree-build loop. N is bounded to at most 285 symbols (WebP
|
|
alphabet limit) and the function is called only during stream header
|
|
construction (once per Huffman group per image). Not a hot per-pixel path.
|
|
|
|
- **PaletteSortMinimizeDeltas() (`src/utils/palette.c`)**: O(N^2) selection
|
|
sort where N = palette size (<=256). Runs once per image at encoder setup.
|
|
Not a per-pixel membership test and N is strictly bounded. Below our
|
|
defect threshold.
|
|
|
|
- **WINDOW_OFFSETS dedup (`src/enc/backward_references_enc.c` line 636-644)**:
|
|
O(W^2) inner loop but W <= WINDOW_OFFSETS_SIZE_MAX = 32. Constant.
|
|
|
|
## MOAD-0002 — Intertangle CLEAN
|
|
|
|
The VP8Encoder / VP8Decoder structs are per-encode/decode-session objects
|
|
passed explicitly. DSP dispatch tables (`VP8DspInit`, `VP8LDspInit`, etc.) are
|
|
global function pointers, but they are protected by per-function mutex/SRW
|
|
locks via the `WEBP_DSP_INIT_FUNC` macro defined in `src/dsp/cpu.h`.
|
|
|
|
## MOAD-0003 — Leaked Context CLEAN
|
|
|
|
No `pthread_key_t`, `__thread`, `thread_local`, or equivalent found.
|
|
`src/utils/thread_utils.c` provides a worker-thread abstraction that passes
|
|
all state through explicit struct pointers, not thread-local storage.
|
|
|
|
## MOAD-0004 — Logged Secret CLEAN
|
|
|
|
libwebp is a pure codec. No authentication flows, HTTP headers, or credential
|
|
material.
|
|
|
|
## MOAD-0005 — Thundering Herd CLEAN
|
|
|
|
DSP init uses mutex-protected lazy initialization (see `WEBP_DSP_INIT` in
|
|
`src/dsp/cpu.h`): SRWLock on Windows, `pthread_mutex_t` on POSIX. The
|
|
guard checks `func##_last_cpuinfo_used != VP8GetCPUInfo` inside the lock,
|
|
preventing concurrent re-initialization. No unguarded get+null+put pattern
|
|
found.
|