From d1c914f869edfc4326e86b1b0c161249196e6900 Mon Sep 17 00:00:00 2001
From: "Steinar H. Gunderson" <sgunderson@bigfoot.com>
Date: Wed, 1 Feb 2017 17:19:18 +0100
Subject: [PATCH] speedhq: fix out-of-bounds write

Certain alpha run lengths (for SHQ1/SHQ3/SHQ5) could be stored in
both long and short versions, and we would only accept the short version,
returning -1 (invalid code) for the others. This could cause an
out-of-bounds write on malicious input, as discovered by
Andreas Cadhalpun during fuzzing.

Fix by simply allowing both versions, leaving no invalid codes
in the alpha VLC.
---
 libavcodec/speedhq.c | 128 +++++++++++++++++++++++++++++++--------------------
 libavcodec/vlc.h     |  15 ++++--
 2 files changed, 89 insertions(+), 54 deletions(-)

diff --git a/libavcodec/speedhq.c b/libavcodec/speedhq.c
index 30160dd3f2..49609342af 100644
--- a/libavcodec/speedhq.c
+++ b/libavcodec/speedhq.c
@@ -196,7 +196,7 @@ static inline int decode_alpha_block(const SHQContext *s, GetBitContext *gb, uin
             UPDATE_CACHE_LE(re, gb);
             GET_VLC(run, re, gb, ff_dc_alpha_run_vlc_le.table, ALPHA_VLC_BITS, 2);
 
-            if (run == 128) break;
+            if (run < 0) break;
             i += run;
             if (i >= 128)
                 return AVERROR_INVALIDDATA;
@@ -474,61 +474,89 @@ static int speedhq_decode_frame(AVCodecContext *avctx,
  */
 static av_cold void compute_alpha_vlcs(void)
 {
-    uint16_t run_code[129], level_code[256];
-    uint8_t run_bits[129], level_bits[256];
-    int run, level;
-
-    for (run = 0; run < 128; run++) {
-        if (!run) {
-            /* 0 -> 0. */
-            run_code[run] = 0;
-            run_bits[run] = 1;
-        } else if (run <= 4) {
-            /* 10xx -> xx plus 1. */
-            run_code[run] = ((run - 1) << 2) | 1;
-            run_bits[run] = 4;
-        } else {
-            /* 111xxxxxxx -> xxxxxxxx. */
-            run_code[run] = (run << 3) | 7;
-            run_bits[run] = 10;
-        }
+    uint16_t run_code[134], level_code[266];
+    uint8_t run_bits[134], level_bits[266];
+    int16_t run_symbols[134], level_symbols[266];
+    int entry, i, sign;
+
+    /* Initialize VLC for alpha run. */
+    entry = 0;
+
+    /* 0 -> 0. */
+    run_code[entry] = 0;
+    run_bits[entry] = 1;
+    run_symbols[entry] = 0;
+    ++entry;
+
+    /* 10xx -> xx plus 1. */
+    for (i = 0; i < 4; ++i) {
+        run_code[entry] = (i << 2) | 1;
+        run_bits[entry] = 4;
+        run_symbols[entry] = i + 1;
+        ++entry;
+    }
+
+    /* 111xxxxxxx -> xxxxxxx. */
+    for (i = 0; i < 128; ++i) {
+        run_code[entry] = (i << 3) | 7;
+        run_bits[entry] = 10;
+        run_symbols[entry] = i;
+        ++entry;
     }
 
     /* 110 -> EOB. */
-    run_code[128] = 3;
-    run_bits[128] = 3;
-
-    INIT_LE_VLC_STATIC(&ff_dc_alpha_run_vlc_le, ALPHA_VLC_BITS, 129,
-                       run_bits, 1, 1,
-                       run_code, 2, 2, 160);
-
-    for (level = 0; level < 256; level++) {
-        int8_t signed_level = (int8_t)level;
-        int abs_signed_level = abs(signed_level);
-        int sign = (signed_level < 0) ? 1 : 0;
-
-        if (abs_signed_level == 1) {
-            /* 1s -> -1 or +1 (depending on sign bit). */
-            level_code[level] = (sign << 1) | 1;
-            level_bits[level] = 2;
-        } else if (abs_signed_level >= 2 && abs_signed_level <= 5) {
-            /* 01sxx -> xx plus 2 (2..5 or -2..-5, depending on sign bit). */
-            level_code[level] = ((abs_signed_level - 2) << 3) | (sign << 2) | 2;
-            level_bits[level] = 5;
-        } else {
-            /*
-             * 00xxxxxxxx -> xxxxxxxx, in two's complement. 0 is technically an
-             * illegal code (that would be encoded by increasing run), but it
-             * doesn't hurt and simplifies indexing.
-             */
-            level_code[level] = level << 2;
-            level_bits[level] = 10;
+    run_code[entry] = 3;
+    run_bits[entry] = 3;
+    run_symbols[entry] = -1;
+    ++entry;
+
+    av_assert0(entry == FF_ARRAY_ELEMS(run_code));
+
+    INIT_LE_VLC_SPARSE_STATIC(&ff_dc_alpha_run_vlc_le, ALPHA_VLC_BITS,
+                              FF_ARRAY_ELEMS(run_code),
+                              run_bits, 1, 1,
+                              run_code, 2, 2,
+                              run_symbols, 2, 2, 160);
+
+    /* Initialize VLC for alpha level. */
+    entry = 0;
+
+    for (sign = 0; sign <= 1; ++sign) {
+        /* 1s -> -1 or +1 (depending on sign bit). */
+        level_code[entry] = (sign << 1) | 1;
+        level_bits[entry] = 2;
+        level_symbols[entry] = sign ? -1 : 1;
+        ++entry;
+
+        /* 01sxx -> xx plus 2 (2..5 or -2..-5, depending on sign bit). */
+        for (i = 0; i < 4; ++i) {
+            level_code[entry] = (i << 3) | (sign << 2) | 2;
+            level_bits[entry] = 5;
+            level_symbols[entry] = sign ? -(i + 2) : (i + 2);
+            ++entry;
         }
     }
 
-    INIT_LE_VLC_STATIC(&ff_dc_alpha_level_vlc_le, ALPHA_VLC_BITS, 256,
-                       level_bits, 1, 1,
-                       level_code, 2, 2, 288);
+    /*
+     * 00xxxxxxxx -> xxxxxxxx, in two's complement. There are many codes
+     * here that would better be encoded in other ways (e.g. 0 would be
+     * encoded by increasing run, and +/- 1 would be encoded with a
+     * shorter code), but it doesn't hurt to allow everything.
+     */
+    for (i = 0; i < 256; ++i) {
+        level_code[entry] = i << 2;
+        level_bits[entry] = 10;
+        level_symbols[entry] = i;
+        ++entry;
+    }
+
+    av_assert0(entry == FF_ARRAY_ELEMS(level_code));
+
+    INIT_LE_VLC_SPARSE_STATIC(&ff_dc_alpha_level_vlc_le, ALPHA_VLC_BITS,
+                              FF_ARRAY_ELEMS(level_code),
+                              level_bits, 1, 1,
+                              level_code, 2, 2,
+                              level_symbols, 2, 2, 288);
 }
 
 static uint32_t reverse(uint32_t num, int bits)
diff --git a/libavcodec/vlc.h b/libavcodec/vlc.h
index 40096d8944..42ccddf3fc 100644
--- a/libavcodec/vlc.h
+++ b/libavcodec/vlc.h
@@ -54,21 +54,28 @@ void ff_free_vlc(VLC *vlc);
 #define INIT_VLC_LE             2
 #define INIT_VLC_USE_NEW_STATIC 4
 
-#define INIT_VLC_STATIC(vlc, bits, a, b, c, d, e, f, g, static_size)       \
+#define INIT_VLC_SPARSE_STATIC(vlc, bits, a, b, c, d, e, f, g, h, i, j, static_size) \
     do {                                                                   \
         static VLC_TYPE table[static_size][2];                             \
         (vlc)->table           = table;                                    \
         (vlc)->table_allocated = static_size;                              \
-        init_vlc(vlc, bits, a, b, c, d, e, f, g, INIT_VLC_USE_NEW_STATIC); \
+        ff_init_vlc_sparse(vlc, bits, a, b, c, d, e, f, g, h, i, j,        \
+            INIT_VLC_USE_NEW_STATIC);                                      \
     } while (0)
 
-#define INIT_LE_VLC_STATIC(vlc, bits, a, b, c, d, e, f, g, static_size)    \
+#define INIT_LE_VLC_SPARSE_STATIC(vlc, bits, a, b, c, d, e, f, g, h, i, j, static_size) \
     do {                                                                   \
         static VLC_TYPE table[static_size][2];                             \
         (vlc)->table           = table;                                    \
         (vlc)->table_allocated = static_size;                              \
-        init_vlc(vlc, bits, a, b, c, d, e, f, g,                           \
+        ff_init_vlc_sparse(vlc, bits, a, b, c, d, e, f, g, h, i, j,        \
             INIT_VLC_USE_NEW_STATIC | INIT_VLC_LE);                        \
     } while (0)
 
+#define INIT_VLC_STATIC(vlc, bits, a, b, c, d, e, f, g, static_size)       \
+    INIT_VLC_SPARSE_STATIC(vlc, bits, a, b, c, d, e, f, g, NULL, 0, 0, static_size)
+
+#define INIT_LE_VLC_STATIC(vlc, bits, a, b, c, d, e, f, g, static_size) \
+    INIT_LE_VLC_SPARSE_STATIC(vlc, bits, a, b, c, d, e, f, g, NULL, 0, 0, static_size)
+
 #endif /* AVCODEC_VLC_H */
-- 
2.11.0

