# ffmpeg-0001 — Codec Tag Linear Scan Per Stream (CWE-407)

**Status:** PATCHED
**Severity:** MEDIUM
**Target:** FFmpeg `libavformat/utils.c`
**Functions:** `ff_codec_get_tag()`, `ff_codec_get_id()`, `av_codec_get_tag2()`

## Defect

`ff_codec_get_tag()` performs an O(N) linear scan over a static `AVCodecTag[]`
array to map a codec ID to a 4-byte FourCC tag.  The arrays are large:

| Table                     | Entries |
|---------------------------|---------|
| `ff_codec_movvideo_tags`  | 239     |
| `ff_codec_bmp_tags`       | 460     |
| `ff_codec_movaudio_tags`  | 60      |
| `ff_codec_wav_tags`       | 85      |

This function is called for **every stream** in every muxer hot path:

- `movenc.c:2135` — `mov_get_codec_tag()` calls it 2–3 times per video/audio track
- `matroskaenc.c:1251,1262,1267,1281` — Matroska mux does the same
- `flvenc.c:260,1012,1296` — FLV encoder
- `cafenc.c:120,153` — CAF encoder
- `au.c:295` — AU encoder

When multiplexing a file with many streams (e.g., a playlist transcode or
broadcast ingest with 50+ streams), this becomes O(S × N) where S = stream
count and N = table size (up to 460).

`ff_codec_get_id()` is worse — it scans the array **twice** (once exact, once
case-insensitive via `ff_toupper4`) for a total of O(2N) per call.

## Root Cause

`AVCodecTag` arrays are statically allocated flat arrays with sentinel
`AV_CODEC_ID_NONE` terminators.  No hash index is built at startup.
Both directions (id→tag and tag→id) are O(N) linear scans.

## Fix

Build a `uint32_t → AVCodecID` and `AVCodecID → uint32_t` hash map
at program startup (or lazily on first call) keyed on codec ID /
FourCC tag.  The arrays are read-only after init; one-time O(N) build
cost, then O(1) lookups.

Patch: `defects/ffmpeg/patch/ffmpeg-0001.patch`

## Complexity

| | Before | After |
|---|---|---|
| `ff_codec_get_tag` | O(N), N≤460 | O(1) amortized |
| `ff_codec_get_id` | O(2N) | O(1) |
| `av_codec_get_tag2` | O(T×N) T=table count | O(1) |

## Benchmark

See `defects/ffmpeg/unit/FFmpegCodecTagTest.java` — at N=500 (synthetic),
the linear scan executes ≥100× more comparisons than the hash map.