1 /* 2 * Copyright (c) 2010 The WebM project authors. All Rights Reserved. 3 * 4 * Use of this source code is governed by a BSD-style license 5 * that can be found in the LICENSE file in the root of the source 6 * tree. An additional intellectual property rights grant can be found 7 * in the file PATENTS. All contributing project authors may 8 * be found in the AUTHORS file in the root of the source tree. 9 */ 10 11 #include "vp9/common/vp9_entropy.h" 12 #include "vp9/common/vp9_blockd.h" 13 #include "vp9/common/vp9_onyxc_int.h" 14 #include "vp9/common/vp9_entropymode.h" 15 #include "vpx_mem/vpx_mem.h" 16 #include "vpx/vpx_integer.h" 17 18 #define MODEL_NODES (ENTROPY_NODES - UNCONSTRAINED_NODES) 19 20 DECLARE_ALIGNED(16, const uint8_t, vp9_norm[256]) = { 21 0, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 22 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 23 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 24 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 25 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 26 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 27 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 28 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 29 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 30 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 31 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 32 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 33 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 34 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 35 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 36 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 37 }; 38 39 DECLARE_ALIGNED(16, const uint8_t, 40 vp9_coefband_trans_8x8plus[MAXBAND_INDEX + 1]) = { 41 0, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 42 4, 4, 4, 4, 4, 5 43 }; 44 45 DECLARE_ALIGNED(16, const uint8_t, 46 vp9_coefband_trans_4x4[MAXBAND_INDEX + 1]) = { 47 0, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 5, 48 5, 5, 5, 5, 5, 5 49 }; 50 51 DECLARE_ALIGNED(16, const uint8_t, vp9_pt_energy_class[MAX_ENTROPY_TOKENS]) = { 52 0, 1, 2, 3, 3, 4, 4, 5, 5, 5, 5, 5 53 }; 54 55 DECLARE_ALIGNED(16, const int16_t, vp9_default_scan_4x4[16]) = { 56 0, 4, 1, 5, 57 8, 2, 12, 9, 58 3, 6, 13, 10, 59 7, 14, 11, 15, 60 }; 61 62 DECLARE_ALIGNED(16, const int16_t, vp9_col_scan_4x4[16]) = { 63 0, 4, 8, 1, 64 12, 5, 9, 2, 65 13, 6, 10, 3, 66 7, 14, 11, 15, 67 }; 68 69 DECLARE_ALIGNED(16, const int16_t, vp9_row_scan_4x4[16]) = { 70 0, 1, 4, 2, 71 5, 3, 6, 8, 72 9, 7, 12, 10, 73 13, 11, 14, 15, 74 }; 75 76 DECLARE_ALIGNED(16, const int16_t, vp9_default_scan_8x8[64]) = { 77 0, 8, 1, 16, 9, 2, 17, 24, 78 10, 3, 18, 25, 32, 11, 4, 26, 79 33, 19, 40, 12, 34, 27, 5, 41, 80 20, 48, 13, 35, 42, 28, 21, 6, 81 49, 56, 36, 43, 29, 7, 14, 50, 82 57, 44, 22, 37, 15, 51, 58, 30, 83 45, 23, 52, 59, 38, 31, 60, 53, 84 46, 39, 61, 54, 47, 62, 55, 63, 85 }; 86 87 DECLARE_ALIGNED(16, const int16_t, vp9_col_scan_8x8[64]) = { 88 0, 8, 16, 1, 24, 9, 32, 17, 89 2, 40, 25, 10, 33, 18, 48, 3, 90 26, 41, 11, 56, 19, 34, 4, 49, 91 27, 42, 12, 35, 20, 57, 50, 28, 92 5, 43, 13, 36, 58, 51, 21, 44, 93 6, 29, 59, 37, 14, 52, 22, 7, 94 45, 60, 30, 15, 38, 53, 23, 46, 95 31, 61, 39, 54, 47, 62, 55, 63, 96 }; 97 98 DECLARE_ALIGNED(16, const int16_t, vp9_row_scan_8x8[64]) = { 99 0, 1, 2, 8, 9, 3, 16, 10, 100 4, 17, 11, 24, 5, 18, 25, 12, 101 19, 26, 32, 6, 13, 20, 33, 27, 102 7, 34, 40, 21, 28, 41, 14, 35, 103 48, 42, 29, 36, 49, 22, 43, 15, 104 56, 37, 50, 44, 30, 57, 23, 51, 105 58, 45, 38, 52, 31, 59, 53, 46, 106 60, 39, 61, 47, 54, 55, 62, 63, 107 }; 108 109 DECLARE_ALIGNED(16, const int16_t, vp9_default_scan_16x16[256]) = { 110 0, 16, 1, 32, 17, 2, 48, 33, 18, 3, 64, 34, 49, 19, 65, 80, 111 50, 4, 35, 66, 20, 81, 96, 51, 5, 36, 82, 97, 67, 112, 21, 52, 112 98, 37, 83, 113, 6, 68, 128, 53, 22, 99, 114, 84, 7, 129, 38, 69, 113 100, 115, 144, 130, 85, 54, 23, 8, 145, 39, 70, 116, 101, 131, 160, 146, 114 55, 86, 24, 71, 132, 117, 161, 40, 9, 102, 147, 176, 162, 87, 56, 25, 115 133, 118, 177, 148, 72, 103, 41, 163, 10, 192, 178, 88, 57, 134, 149, 119, 116 26, 164, 73, 104, 193, 42, 179, 208, 11, 135, 89, 165, 120, 150, 58, 194, 117 180, 27, 74, 209, 105, 151, 136, 43, 90, 224, 166, 195, 181, 121, 210, 59, 118 12, 152, 106, 167, 196, 75, 137, 225, 211, 240, 182, 122, 91, 28, 197, 13, 119 226, 168, 183, 153, 44, 212, 138, 107, 241, 60, 29, 123, 198, 184, 227, 169, 120 242, 76, 213, 154, 45, 92, 14, 199, 139, 61, 228, 214, 170, 185, 243, 108, 121 77, 155, 30, 15, 200, 229, 124, 215, 244, 93, 46, 186, 171, 201, 109, 140, 122 230, 62, 216, 245, 31, 125, 78, 156, 231, 47, 187, 202, 217, 94, 246, 141, 123 63, 232, 172, 110, 247, 157, 79, 218, 203, 126, 233, 188, 248, 95, 173, 142, 124 219, 111, 249, 234, 158, 127, 189, 204, 250, 235, 143, 174, 220, 205, 159, 251, 125 190, 221, 175, 236, 237, 191, 206, 252, 222, 253, 207, 238, 223, 254, 239, 255, 126 }; 127 128 DECLARE_ALIGNED(16, const int16_t, vp9_col_scan_16x16[256]) = { 129 0, 16, 32, 48, 1, 64, 17, 80, 33, 96, 49, 2, 65, 112, 18, 81, 130 34, 128, 50, 97, 3, 66, 144, 19, 113, 35, 82, 160, 98, 51, 129, 4, 131 67, 176, 20, 114, 145, 83, 36, 99, 130, 52, 192, 5, 161, 68, 115, 21, 132 146, 84, 208, 177, 37, 131, 100, 53, 162, 224, 69, 6, 116, 193, 147, 85, 133 22, 240, 132, 38, 178, 101, 163, 54, 209, 117, 70, 7, 148, 194, 86, 179, 134 225, 23, 133, 39, 164, 8, 102, 210, 241, 55, 195, 118, 149, 71, 180, 24, 135 87, 226, 134, 165, 211, 40, 103, 56, 72, 150, 196, 242, 119, 9, 181, 227, 136 88, 166, 25, 135, 41, 104, 212, 57, 151, 197, 120, 73, 243, 182, 136, 167, 137 213, 89, 10, 228, 105, 152, 198, 26, 42, 121, 183, 244, 168, 58, 137, 229, 138 74, 214, 90, 153, 199, 184, 11, 106, 245, 27, 122, 230, 169, 43, 215, 59, 139 200, 138, 185, 246, 75, 12, 91, 154, 216, 231, 107, 28, 44, 201, 123, 170, 140 60, 247, 232, 76, 139, 13, 92, 217, 186, 248, 155, 108, 29, 124, 45, 202, 141 233, 171, 61, 14, 77, 140, 15, 249, 93, 30, 187, 156, 218, 46, 109, 125, 142 62, 172, 78, 203, 31, 141, 234, 94, 47, 188, 63, 157, 110, 250, 219, 79, 143 126, 204, 173, 142, 95, 189, 111, 235, 158, 220, 251, 127, 174, 143, 205, 236, 144 159, 190, 221, 252, 175, 206, 237, 191, 253, 222, 238, 207, 254, 223, 239, 255, 145 }; 146 147 DECLARE_ALIGNED(16, const int16_t, vp9_row_scan_16x16[256]) = { 148 0, 1, 2, 16, 3, 17, 4, 18, 32, 5, 33, 19, 6, 34, 48, 20, 149 49, 7, 35, 21, 50, 64, 8, 36, 65, 22, 51, 37, 80, 9, 66, 52, 150 23, 38, 81, 67, 10, 53, 24, 82, 68, 96, 39, 11, 54, 83, 97, 69, 151 25, 98, 84, 40, 112, 55, 12, 70, 99, 113, 85, 26, 41, 56, 114, 100, 152 13, 71, 128, 86, 27, 115, 101, 129, 42, 57, 72, 116, 14, 87, 130, 102, 153 144, 73, 131, 117, 28, 58, 15, 88, 43, 145, 103, 132, 146, 118, 74, 160, 154 89, 133, 104, 29, 59, 147, 119, 44, 161, 148, 90, 105, 134, 162, 120, 176, 155 75, 135, 149, 30, 60, 163, 177, 45, 121, 91, 106, 164, 178, 150, 192, 136, 156 165, 179, 31, 151, 193, 76, 122, 61, 137, 194, 107, 152, 180, 208, 46, 166, 157 167, 195, 92, 181, 138, 209, 123, 153, 224, 196, 77, 168, 210, 182, 240, 108, 158 197, 62, 154, 225, 183, 169, 211, 47, 139, 93, 184, 226, 212, 241, 198, 170, 159 124, 155, 199, 78, 213, 185, 109, 227, 200, 63, 228, 242, 140, 214, 171, 186, 160 156, 229, 243, 125, 94, 201, 244, 215, 216, 230, 141, 187, 202, 79, 172, 110, 161 157, 245, 217, 231, 95, 246, 232, 126, 203, 247, 233, 173, 218, 142, 111, 158, 162 188, 248, 127, 234, 219, 249, 189, 204, 143, 174, 159, 250, 235, 205, 220, 175, 163 190, 251, 221, 191, 206, 236, 207, 237, 252, 222, 253, 223, 238, 239, 254, 255, 164 }; 165 166 DECLARE_ALIGNED(16, const int16_t, vp9_default_scan_32x32[1024]) = { 167 0, 32, 1, 64, 33, 2, 96, 65, 34, 128, 3, 97, 66, 160, 129, 35, 98, 4, 67, 130, 161, 192, 36, 99, 224, 5, 162, 193, 68, 131, 37, 100, 168 225, 194, 256, 163, 69, 132, 6, 226, 257, 288, 195, 101, 164, 38, 258, 7, 227, 289, 133, 320, 70, 196, 165, 290, 259, 228, 39, 321, 102, 352, 8, 197, 169 71, 134, 322, 291, 260, 353, 384, 229, 166, 103, 40, 354, 323, 292, 135, 385, 198, 261, 72, 9, 416, 167, 386, 355, 230, 324, 104, 293, 41, 417, 199, 136, 170 262, 387, 448, 325, 356, 10, 73, 418, 231, 168, 449, 294, 388, 105, 419, 263, 42, 200, 357, 450, 137, 480, 74, 326, 232, 11, 389, 169, 295, 420, 106, 451, 171 481, 358, 264, 327, 201, 43, 138, 512, 482, 390, 296, 233, 170, 421, 75, 452, 359, 12, 513, 265, 483, 328, 107, 202, 514, 544, 422, 391, 453, 139, 44, 234, 172 484, 297, 360, 171, 76, 515, 545, 266, 329, 454, 13, 423, 203, 108, 546, 485, 576, 298, 235, 140, 361, 330, 172, 547, 45, 455, 267, 577, 486, 77, 204, 362, 173 608, 14, 299, 578, 109, 236, 487, 609, 331, 141, 579, 46, 15, 173, 610, 363, 78, 205, 16, 110, 237, 611, 142, 47, 174, 79, 206, 17, 111, 238, 48, 143, 174 80, 175, 112, 207, 49, 18, 239, 81, 113, 19, 50, 82, 114, 51, 83, 115, 640, 516, 392, 268, 144, 20, 672, 641, 548, 517, 424, 393, 300, 269, 176, 145, 175 52, 21, 704, 673, 642, 580, 549, 518, 456, 425, 394, 332, 301, 270, 208, 177, 146, 84, 53, 22, 736, 705, 674, 643, 612, 581, 550, 519, 488, 457, 426, 395, 176 364, 333, 302, 271, 240, 209, 178, 147, 116, 85, 54, 23, 737, 706, 675, 613, 582, 551, 489, 458, 427, 365, 334, 303, 241, 210, 179, 117, 86, 55, 738, 707, 177 614, 583, 490, 459, 366, 335, 242, 211, 118, 87, 739, 615, 491, 367, 243, 119, 768, 644, 520, 396, 272, 148, 24, 800, 769, 676, 645, 552, 521, 428, 397, 304, 178 273, 180, 149, 56, 25, 832, 801, 770, 708, 677, 646, 584, 553, 522, 460, 429, 398, 336, 305, 274, 212, 181, 150, 88, 57, 26, 864, 833, 802, 771, 740, 709, 179 678, 647, 616, 585, 554, 523, 492, 461, 430, 399, 368, 337, 306, 275, 244, 213, 182, 151, 120, 89, 58, 27, 865, 834, 803, 741, 710, 679, 617, 586, 555, 493, 180 462, 431, 369, 338, 307, 245, 214, 183, 121, 90, 59, 866, 835, 742, 711, 618, 587, 494, 463, 370, 339, 246, 215, 122, 91, 867, 743, 619, 495, 371, 247, 123, 181 896, 772, 648, 524, 400, 276, 152, 28, 928, 897, 804, 773, 680, 649, 556, 525, 432, 401, 308, 277, 184, 153, 60, 29, 960, 929, 898, 836, 805, 774, 712, 681, 182 650, 588, 557, 526, 464, 433, 402, 340, 309, 278, 216, 185, 154, 92, 61, 30, 992, 961, 930, 899, 868, 837, 806, 775, 744, 713, 682, 651, 620, 589, 558, 527, 183 496, 465, 434, 403, 372, 341, 310, 279, 248, 217, 186, 155, 124, 93, 62, 31, 993, 962, 931, 869, 838, 807, 745, 714, 683, 621, 590, 559, 497, 466, 435, 373, 184 342, 311, 249, 218, 187, 125, 94, 63, 994, 963, 870, 839, 746, 715, 622, 591, 498, 467, 374, 343, 250, 219, 126, 95, 995, 871, 747, 623, 499, 375, 251, 127, 185 900, 776, 652, 528, 404, 280, 156, 932, 901, 808, 777, 684, 653, 560, 529, 436, 405, 312, 281, 188, 157, 964, 933, 902, 840, 809, 778, 716, 685, 654, 592, 561, 186 530, 468, 437, 406, 344, 313, 282, 220, 189, 158, 996, 965, 934, 903, 872, 841, 810, 779, 748, 717, 686, 655, 624, 593, 562, 531, 500, 469, 438, 407, 376, 345, 187 314, 283, 252, 221, 190, 159, 997, 966, 935, 873, 842, 811, 749, 718, 687, 625, 594, 563, 501, 470, 439, 377, 346, 315, 253, 222, 191, 998, 967, 874, 843, 750, 188 719, 626, 595, 502, 471, 378, 347, 254, 223, 999, 875, 751, 627, 503, 379, 255, 904, 780, 656, 532, 408, 284, 936, 905, 812, 781, 688, 657, 564, 533, 440, 409, 189 316, 285, 968, 937, 906, 844, 813, 782, 720, 689, 658, 596, 565, 534, 472, 441, 410, 348, 317, 286, 1000, 969, 938, 907, 876, 845, 814, 783, 752, 721, 690, 659, 190 628, 597, 566, 535, 504, 473, 442, 411, 380, 349, 318, 287, 1001, 970, 939, 877, 846, 815, 753, 722, 691, 629, 598, 567, 505, 474, 443, 381, 350, 319, 1002, 971, 191 878, 847, 754, 723, 630, 599, 506, 475, 382, 351, 1003, 879, 755, 631, 507, 383, 908, 784, 660, 536, 412, 940, 909, 816, 785, 692, 661, 568, 537, 444, 413, 972, 192 941, 910, 848, 817, 786, 724, 693, 662, 600, 569, 538, 476, 445, 414, 1004, 973, 942, 911, 880, 849, 818, 787, 756, 725, 694, 663, 632, 601, 570, 539, 508, 477, 193 446, 415, 1005, 974, 943, 881, 850, 819, 757, 726, 695, 633, 602, 571, 509, 478, 447, 1006, 975, 882, 851, 758, 727, 634, 603, 510, 479, 1007, 883, 759, 635, 511, 194 912, 788, 664, 540, 944, 913, 820, 789, 696, 665, 572, 541, 976, 945, 914, 852, 821, 790, 728, 697, 666, 604, 573, 542, 1008, 977, 946, 915, 884, 853, 822, 791, 195 760, 729, 698, 667, 636, 605, 574, 543, 1009, 978, 947, 885, 854, 823, 761, 730, 699, 637, 606, 575, 1010, 979, 886, 855, 762, 731, 638, 607, 1011, 887, 763, 639, 196 916, 792, 668, 948, 917, 824, 793, 700, 669, 980, 949, 918, 856, 825, 794, 732, 701, 670, 1012, 981, 950, 919, 888, 857, 826, 795, 764, 733, 702, 671, 1013, 982, 197 951, 889, 858, 827, 765, 734, 703, 1014, 983, 890, 859, 766, 735, 1015, 891, 767, 920, 796, 952, 921, 828, 797, 984, 953, 922, 860, 829, 798, 1016, 985, 954, 923, 198 892, 861, 830, 799, 1017, 986, 955, 893, 862, 831, 1018, 987, 894, 863, 1019, 895, 924, 956, 925, 988, 957, 926, 1020, 989, 958, 927, 1021, 990, 959, 1022, 991, 1023, 199 }; 200 201 /* Array indices are identical to previously-existing CONTEXT_NODE indices */ 202 203 const vp9_tree_index vp9_coef_tree[ 22] = /* corresponding _CONTEXT_NODEs */ 204 { 205 -DCT_EOB_TOKEN, 2, /* 0 = EOB */ 206 -ZERO_TOKEN, 4, /* 1 = ZERO */ 207 -ONE_TOKEN, 6, /* 2 = ONE */ 208 8, 12, /* 3 = LOW_VAL */ 209 -TWO_TOKEN, 10, /* 4 = TWO */ 210 -THREE_TOKEN, -FOUR_TOKEN, /* 5 = THREE */ 211 14, 16, /* 6 = HIGH_LOW */ 212 -DCT_VAL_CATEGORY1, -DCT_VAL_CATEGORY2, /* 7 = CAT_ONE */ 213 18, 20, /* 8 = CAT_THREEFOUR */ 214 -DCT_VAL_CATEGORY3, -DCT_VAL_CATEGORY4, /* 9 = CAT_THREE */ 215 -DCT_VAL_CATEGORY5, -DCT_VAL_CATEGORY6 /* 10 = CAT_FIVE */ 216 }; 217 218 struct vp9_token vp9_coef_encodings[MAX_ENTROPY_TOKENS]; 219 220 /* Trees for extra bits. Probabilities are constant and 221 do not depend on previously encoded bits */ 222 223 static const vp9_prob Pcat1[] = { 159}; 224 static const vp9_prob Pcat2[] = { 165, 145}; 225 static const vp9_prob Pcat3[] = { 173, 148, 140}; 226 static const vp9_prob Pcat4[] = { 176, 155, 140, 135}; 227 static const vp9_prob Pcat5[] = { 180, 157, 141, 134, 130}; 228 static const vp9_prob Pcat6[] = { 229 254, 254, 254, 252, 249, 243, 230, 196, 177, 153, 140, 133, 130, 129 230 }; 231 232 const vp9_tree_index vp9_coefmodel_tree[6] = { 233 -DCT_EOB_MODEL_TOKEN, 2, /* 0 = EOB */ 234 -ZERO_TOKEN, 4, /* 1 = ZERO */ 235 -ONE_TOKEN, -TWO_TOKEN, 236 }; 237 238 // Model obtained from a 2-sided zero-centerd distribuition derived 239 // from a Pareto distribution. The cdf of the distribution is: 240 // cdf(x) = 0.5 + 0.5 * sgn(x) * [1 - {alpha/(alpha + |x|)} ^ beta] 241 // 242 // For a given beta and a given probablity of the 1-node, the alpha 243 // is first solved, and then the {alpha, beta} pair is used to generate 244 // the probabilities for the rest of the nodes. 245 246 // beta = 8 247 static const vp9_prob modelcoefprobs_pareto8[COEFPROB_MODELS][MODEL_NODES] = { 248 { 3, 86, 128, 6, 86, 23, 88, 29}, 249 { 9, 86, 129, 17, 88, 61, 94, 76}, 250 { 15, 87, 129, 28, 89, 93, 100, 110}, 251 { 20, 88, 130, 38, 91, 118, 106, 136}, 252 { 26, 89, 131, 48, 92, 139, 111, 156}, 253 { 31, 90, 131, 58, 94, 156, 117, 171}, 254 { 37, 90, 132, 66, 95, 171, 122, 184}, 255 { 42, 91, 132, 75, 97, 183, 127, 194}, 256 { 47, 92, 133, 83, 98, 193, 132, 202}, 257 { 52, 93, 133, 90, 100, 201, 137, 208}, 258 { 57, 94, 134, 98, 101, 208, 142, 214}, 259 { 62, 94, 135, 105, 103, 214, 146, 218}, 260 { 66, 95, 135, 111, 104, 219, 151, 222}, 261 { 71, 96, 136, 117, 106, 224, 155, 225}, 262 { 76, 97, 136, 123, 107, 227, 159, 228}, 263 { 80, 98, 137, 129, 109, 231, 162, 231}, 264 { 84, 98, 138, 134, 110, 234, 166, 233}, 265 { 89, 99, 138, 140, 112, 236, 170, 235}, 266 { 93, 100, 139, 145, 113, 238, 173, 236}, 267 { 97, 101, 140, 149, 115, 240, 176, 238}, 268 {101, 102, 140, 154, 116, 242, 179, 239}, 269 {105, 103, 141, 158, 118, 243, 182, 240}, 270 {109, 104, 141, 162, 119, 244, 185, 241}, 271 {113, 104, 142, 166, 120, 245, 187, 242}, 272 {116, 105, 143, 170, 122, 246, 190, 243}, 273 {120, 106, 143, 173, 123, 247, 192, 244}, 274 {123, 107, 144, 177, 125, 248, 195, 244}, 275 {127, 108, 145, 180, 126, 249, 197, 245}, 276 {130, 109, 145, 183, 128, 249, 199, 245}, 277 {134, 110, 146, 186, 129, 250, 201, 246}, 278 {137, 111, 147, 189, 131, 251, 203, 246}, 279 {140, 112, 147, 192, 132, 251, 205, 247}, 280 {143, 113, 148, 194, 133, 251, 207, 247}, 281 {146, 114, 149, 197, 135, 252, 208, 248}, 282 {149, 115, 149, 199, 136, 252, 210, 248}, 283 {152, 115, 150, 201, 138, 252, 211, 248}, 284 {155, 116, 151, 204, 139, 253, 213, 249}, 285 {158, 117, 151, 206, 140, 253, 214, 249}, 286 {161, 118, 152, 208, 142, 253, 216, 249}, 287 {163, 119, 153, 210, 143, 253, 217, 249}, 288 {166, 120, 153, 212, 144, 254, 218, 250}, 289 {168, 121, 154, 213, 146, 254, 220, 250}, 290 {171, 122, 155, 215, 147, 254, 221, 250}, 291 {173, 123, 155, 217, 148, 254, 222, 250}, 292 {176, 124, 156, 218, 150, 254, 223, 250}, 293 {178, 125, 157, 220, 151, 254, 224, 251}, 294 {180, 126, 157, 221, 152, 254, 225, 251}, 295 {183, 127, 158, 222, 153, 254, 226, 251}, 296 {185, 128, 159, 224, 155, 255, 227, 251}, 297 {187, 129, 160, 225, 156, 255, 228, 251}, 298 {189, 131, 160, 226, 157, 255, 228, 251}, 299 {191, 132, 161, 227, 159, 255, 229, 251}, 300 {193, 133, 162, 228, 160, 255, 230, 252}, 301 {195, 134, 163, 230, 161, 255, 231, 252}, 302 {197, 135, 163, 231, 162, 255, 231, 252}, 303 {199, 136, 164, 232, 163, 255, 232, 252}, 304 {201, 137, 165, 233, 165, 255, 233, 252}, 305 {202, 138, 166, 233, 166, 255, 233, 252}, 306 {204, 139, 166, 234, 167, 255, 234, 252}, 307 {206, 140, 167, 235, 168, 255, 235, 252}, 308 {207, 141, 168, 236, 169, 255, 235, 252}, 309 {209, 142, 169, 237, 171, 255, 236, 252}, 310 {210, 144, 169, 237, 172, 255, 236, 252}, 311 {212, 145, 170, 238, 173, 255, 237, 252}, 312 {214, 146, 171, 239, 174, 255, 237, 253}, 313 {215, 147, 172, 240, 175, 255, 238, 253}, 314 {216, 148, 173, 240, 176, 255, 238, 253}, 315 {218, 149, 173, 241, 177, 255, 239, 253}, 316 {219, 150, 174, 241, 179, 255, 239, 253}, 317 {220, 152, 175, 242, 180, 255, 240, 253}, 318 {222, 153, 176, 242, 181, 255, 240, 253}, 319 {223, 154, 177, 243, 182, 255, 240, 253}, 320 {224, 155, 178, 244, 183, 255, 241, 253}, 321 {225, 156, 178, 244, 184, 255, 241, 253}, 322 {226, 158, 179, 244, 185, 255, 242, 253}, 323 {228, 159, 180, 245, 186, 255, 242, 253}, 324 {229, 160, 181, 245, 187, 255, 242, 253}, 325 {230, 161, 182, 246, 188, 255, 243, 253}, 326 {231, 163, 183, 246, 189, 255, 243, 253}, 327 {232, 164, 184, 247, 190, 255, 243, 253}, 328 {233, 165, 185, 247, 191, 255, 244, 253}, 329 {234, 166, 185, 247, 192, 255, 244, 253}, 330 {235, 168, 186, 248, 193, 255, 244, 253}, 331 {236, 169, 187, 248, 194, 255, 244, 253}, 332 {236, 170, 188, 248, 195, 255, 245, 253}, 333 {237, 171, 189, 249, 196, 255, 245, 254}, 334 {238, 173, 190, 249, 197, 255, 245, 254}, 335 {239, 174, 191, 249, 198, 255, 245, 254}, 336 {240, 175, 192, 249, 199, 255, 246, 254}, 337 {240, 177, 193, 250, 200, 255, 246, 254}, 338 {241, 178, 194, 250, 201, 255, 246, 254}, 339 {242, 179, 195, 250, 202, 255, 246, 254}, 340 {242, 181, 196, 250, 203, 255, 247, 254}, 341 {243, 182, 197, 251, 204, 255, 247, 254}, 342 {244, 184, 198, 251, 205, 255, 247, 254}, 343 {244, 185, 199, 251, 206, 255, 247, 254}, 344 {245, 186, 200, 251, 207, 255, 247, 254}, 345 {246, 188, 201, 252, 207, 255, 248, 254}, 346 {246, 189, 202, 252, 208, 255, 248, 254}, 347 {247, 191, 203, 252, 209, 255, 248, 254}, 348 {247, 192, 204, 252, 210, 255, 248, 254}, 349 {248, 194, 205, 252, 211, 255, 248, 254}, 350 {248, 195, 206, 252, 212, 255, 249, 254}, 351 {249, 197, 207, 253, 213, 255, 249, 254}, 352 {249, 198, 208, 253, 214, 255, 249, 254}, 353 {250, 200, 210, 253, 215, 255, 249, 254}, 354 {250, 201, 211, 253, 215, 255, 249, 254}, 355 {250, 203, 212, 253, 216, 255, 249, 254}, 356 {251, 204, 213, 253, 217, 255, 250, 254}, 357 {251, 206, 214, 254, 218, 255, 250, 254}, 358 {252, 207, 216, 254, 219, 255, 250, 254}, 359 {252, 209, 217, 254, 220, 255, 250, 254}, 360 {252, 211, 218, 254, 221, 255, 250, 254}, 361 {253, 213, 219, 254, 222, 255, 250, 254}, 362 {253, 214, 221, 254, 223, 255, 250, 254}, 363 {253, 216, 222, 254, 224, 255, 251, 254}, 364 {253, 218, 224, 254, 225, 255, 251, 254}, 365 {254, 220, 225, 254, 225, 255, 251, 254}, 366 {254, 222, 227, 255, 226, 255, 251, 254}, 367 {254, 224, 228, 255, 227, 255, 251, 254}, 368 {254, 226, 230, 255, 228, 255, 251, 254}, 369 {255, 228, 231, 255, 230, 255, 251, 254}, 370 {255, 230, 233, 255, 231, 255, 252, 254}, 371 {255, 232, 235, 255, 232, 255, 252, 254}, 372 {255, 235, 237, 255, 233, 255, 252, 254}, 373 {255, 238, 240, 255, 235, 255, 252, 255}, 374 {255, 241, 243, 255, 236, 255, 252, 254}, 375 {255, 246, 247, 255, 239, 255, 253, 255} 376 }; 377 378 static void extend_model_to_full_distribution(vp9_prob p, 379 vp9_prob *tree_probs) { 380 const int l = (p - 1) / 2; 381 const vp9_prob (*model)[MODEL_NODES] = modelcoefprobs_pareto8; 382 if (p & 1) { 383 vpx_memcpy(tree_probs + UNCONSTRAINED_NODES, 384 model[l], MODEL_NODES * sizeof(vp9_prob)); 385 } else { 386 // interpolate 387 int i; 388 for (i = UNCONSTRAINED_NODES; i < ENTROPY_NODES; ++i) 389 tree_probs[i] = (model[l][i - UNCONSTRAINED_NODES] + 390 model[l + 1][i - UNCONSTRAINED_NODES]) >> 1; 391 } 392 } 393 394 void vp9_model_to_full_probs(const vp9_prob *model, vp9_prob *full) { 395 if (full != model) 396 vpx_memcpy(full, model, sizeof(vp9_prob) * UNCONSTRAINED_NODES); 397 extend_model_to_full_distribution(model[PIVOT_NODE], full); 398 } 399 400 static vp9_tree_index cat1[2], cat2[4], cat3[6], cat4[8], cat5[10], cat6[28]; 401 402 static void init_bit_tree(vp9_tree_index *p, int n) { 403 int i = 0; 404 405 while (++i < n) { 406 p[0] = p[1] = i << 1; 407 p += 2; 408 } 409 410 p[0] = p[1] = 0; 411 } 412 413 static void init_bit_trees() { 414 init_bit_tree(cat1, 1); 415 init_bit_tree(cat2, 2); 416 init_bit_tree(cat3, 3); 417 init_bit_tree(cat4, 4); 418 init_bit_tree(cat5, 5); 419 init_bit_tree(cat6, 14); 420 } 421 422 const vp9_extra_bit vp9_extra_bits[12] = { 423 { 0, 0, 0, 0}, 424 { 0, 0, 0, 1}, 425 { 0, 0, 0, 2}, 426 { 0, 0, 0, 3}, 427 { 0, 0, 0, 4}, 428 { cat1, Pcat1, 1, 5}, 429 { cat2, Pcat2, 2, 7}, 430 { cat3, Pcat3, 3, 11}, 431 { cat4, Pcat4, 4, 19}, 432 { cat5, Pcat5, 5, 35}, 433 { cat6, Pcat6, 14, 67}, 434 { 0, 0, 0, 0} 435 }; 436 437 #include "vp9/common/vp9_default_coef_probs.h" 438 439 void vp9_default_coef_probs(VP9_COMMON *cm) { 440 vp9_copy(cm->fc.coef_probs[TX_4X4], default_coef_probs_4x4); 441 vp9_copy(cm->fc.coef_probs[TX_8X8], default_coef_probs_8x8); 442 vp9_copy(cm->fc.coef_probs[TX_16X16], default_coef_probs_16x16); 443 vp9_copy(cm->fc.coef_probs[TX_32X32], default_coef_probs_32x32); 444 } 445 446 // Neighborhood 5-tuples for various scans and blocksizes, 447 // in {top, left, topleft, topright, bottomleft} order 448 // for each position in raster scan order. 449 // -1 indicates the neighbor does not exist. 450 DECLARE_ALIGNED(16, int16_t, 451 vp9_default_scan_4x4_neighbors[17 * MAX_NEIGHBORS]); 452 DECLARE_ALIGNED(16, int16_t, 453 vp9_col_scan_4x4_neighbors[17 * MAX_NEIGHBORS]); 454 DECLARE_ALIGNED(16, int16_t, 455 vp9_row_scan_4x4_neighbors[17 * MAX_NEIGHBORS]); 456 DECLARE_ALIGNED(16, int16_t, 457 vp9_col_scan_8x8_neighbors[65 * MAX_NEIGHBORS]); 458 DECLARE_ALIGNED(16, int16_t, 459 vp9_row_scan_8x8_neighbors[65 * MAX_NEIGHBORS]); 460 DECLARE_ALIGNED(16, int16_t, 461 vp9_default_scan_8x8_neighbors[65 * MAX_NEIGHBORS]); 462 DECLARE_ALIGNED(16, int16_t, 463 vp9_col_scan_16x16_neighbors[257 * MAX_NEIGHBORS]); 464 DECLARE_ALIGNED(16, int16_t, 465 vp9_row_scan_16x16_neighbors[257 * MAX_NEIGHBORS]); 466 DECLARE_ALIGNED(16, int16_t, 467 vp9_default_scan_16x16_neighbors[257 * MAX_NEIGHBORS]); 468 DECLARE_ALIGNED(16, int16_t, 469 vp9_default_scan_32x32_neighbors[1025 * MAX_NEIGHBORS]); 470 471 DECLARE_ALIGNED(16, int16_t, vp9_default_iscan_4x4[16]); 472 DECLARE_ALIGNED(16, int16_t, vp9_col_iscan_4x4[16]); 473 DECLARE_ALIGNED(16, int16_t, vp9_row_iscan_4x4[16]); 474 DECLARE_ALIGNED(16, int16_t, vp9_col_iscan_8x8[64]); 475 DECLARE_ALIGNED(16, int16_t, vp9_row_iscan_8x8[64]); 476 DECLARE_ALIGNED(16, int16_t, vp9_default_iscan_8x8[64]); 477 DECLARE_ALIGNED(16, int16_t, vp9_col_iscan_16x16[256]); 478 DECLARE_ALIGNED(16, int16_t, vp9_row_iscan_16x16[256]); 479 DECLARE_ALIGNED(16, int16_t, vp9_default_iscan_16x16[256]); 480 DECLARE_ALIGNED(16, int16_t, vp9_default_iscan_32x32[1024]); 481 482 static int find_in_scan(const int16_t *scan, int l, int idx) { 483 int n, l2 = l * l; 484 for (n = 0; n < l2; n++) { 485 int rc = scan[n]; 486 if (rc == idx) 487 return n; 488 } 489 assert(0); 490 return -1; 491 } 492 static void init_scan_neighbors(const int16_t *scan, 493 int16_t *iscan, 494 int l, int16_t *neighbors) { 495 int l2 = l * l; 496 int n, i, j; 497 498 // dc doesn't use this type of prediction 499 neighbors[MAX_NEIGHBORS * 0 + 0] = 0; 500 neighbors[MAX_NEIGHBORS * 0 + 1] = 0; 501 iscan[0] = find_in_scan(scan, l, 0); 502 for (n = 1; n < l2; n++) { 503 int rc = scan[n]; 504 iscan[n] = find_in_scan(scan, l, n); 505 i = rc / l; 506 j = rc % l; 507 if (i > 0 && j > 0) { 508 // col/row scan is used for adst/dct, and generally means that 509 // energy decreases to zero much faster in the dimension in 510 // which ADST is used compared to the direction in which DCT 511 // is used. Likewise, we find much higher correlation between 512 // coefficients within the direction in which DCT is used. 513 // Therefore, if we use ADST/DCT, prefer the DCT neighbor coeff 514 // as a context. If ADST or DCT is used in both directions, we 515 // use the combination of the two as a context. 516 int a = (i - 1) * l + j; 517 int b = i * l + j - 1; 518 if (scan == vp9_col_scan_4x4 || scan == vp9_col_scan_8x8 || 519 scan == vp9_col_scan_16x16) { 520 // in the col/row scan cases (as well as left/top edge cases), we set 521 // both contexts to the same value, so we can branchlessly do a+b+1>>1 522 // which automatically becomes a if a == b 523 neighbors[MAX_NEIGHBORS * n + 0] = 524 neighbors[MAX_NEIGHBORS * n + 1] = a; 525 } else if (scan == vp9_row_scan_4x4 || scan == vp9_row_scan_8x8 || 526 scan == vp9_row_scan_16x16) { 527 neighbors[MAX_NEIGHBORS * n + 0] = 528 neighbors[MAX_NEIGHBORS * n + 1] = b; 529 } else { 530 neighbors[MAX_NEIGHBORS * n + 0] = a; 531 neighbors[MAX_NEIGHBORS * n + 1] = b; 532 } 533 } else if (i > 0) { 534 neighbors[MAX_NEIGHBORS * n + 0] = 535 neighbors[MAX_NEIGHBORS * n + 1] = (i - 1) * l + j; 536 } else { 537 assert(j > 0); 538 neighbors[MAX_NEIGHBORS * n + 0] = 539 neighbors[MAX_NEIGHBORS * n + 1] = i * l + j - 1; 540 } 541 assert(iscan[neighbors[MAX_NEIGHBORS * n + 0]] < n); 542 } 543 // one padding item so we don't have to add branches in code to handle 544 // calls to get_coef_context() for the token after the final dc token 545 neighbors[MAX_NEIGHBORS * l2 + 0] = 0; 546 neighbors[MAX_NEIGHBORS * l2 + 1] = 0; 547 } 548 549 void vp9_init_neighbors() { 550 init_scan_neighbors(vp9_default_scan_4x4, vp9_default_iscan_4x4, 4, 551 vp9_default_scan_4x4_neighbors); 552 init_scan_neighbors(vp9_row_scan_4x4, vp9_row_iscan_4x4, 4, 553 vp9_row_scan_4x4_neighbors); 554 init_scan_neighbors(vp9_col_scan_4x4, vp9_col_iscan_4x4, 4, 555 vp9_col_scan_4x4_neighbors); 556 init_scan_neighbors(vp9_default_scan_8x8, vp9_default_iscan_8x8, 8, 557 vp9_default_scan_8x8_neighbors); 558 init_scan_neighbors(vp9_row_scan_8x8, vp9_row_iscan_8x8, 8, 559 vp9_row_scan_8x8_neighbors); 560 init_scan_neighbors(vp9_col_scan_8x8, vp9_col_iscan_8x8, 8, 561 vp9_col_scan_8x8_neighbors); 562 init_scan_neighbors(vp9_default_scan_16x16, vp9_default_iscan_16x16, 16, 563 vp9_default_scan_16x16_neighbors); 564 init_scan_neighbors(vp9_row_scan_16x16, vp9_row_iscan_16x16, 16, 565 vp9_row_scan_16x16_neighbors); 566 init_scan_neighbors(vp9_col_scan_16x16, vp9_col_iscan_16x16, 16, 567 vp9_col_scan_16x16_neighbors); 568 init_scan_neighbors(vp9_default_scan_32x32, vp9_default_iscan_32x32, 32, 569 vp9_default_scan_32x32_neighbors); 570 } 571 572 const int16_t *vp9_get_coef_neighbors_handle(const int16_t *scan) { 573 if (scan == vp9_default_scan_4x4) { 574 return vp9_default_scan_4x4_neighbors; 575 } else if (scan == vp9_row_scan_4x4) { 576 return vp9_row_scan_4x4_neighbors; 577 } else if (scan == vp9_col_scan_4x4) { 578 return vp9_col_scan_4x4_neighbors; 579 } else if (scan == vp9_default_scan_8x8) { 580 return vp9_default_scan_8x8_neighbors; 581 } else if (scan == vp9_row_scan_8x8) { 582 return vp9_row_scan_8x8_neighbors; 583 } else if (scan == vp9_col_scan_8x8) { 584 return vp9_col_scan_8x8_neighbors; 585 } else if (scan == vp9_default_scan_16x16) { 586 return vp9_default_scan_16x16_neighbors; 587 } else if (scan == vp9_row_scan_16x16) { 588 return vp9_row_scan_16x16_neighbors; 589 } else if (scan == vp9_col_scan_16x16) { 590 return vp9_col_scan_16x16_neighbors; 591 } else { 592 assert(scan == vp9_default_scan_32x32); 593 return vp9_default_scan_32x32_neighbors; 594 } 595 } 596 597 void vp9_coef_tree_initialize() { 598 vp9_init_neighbors(); 599 init_bit_trees(); 600 vp9_tokens_from_tree(vp9_coef_encodings, vp9_coef_tree); 601 } 602 603 // #define COEF_COUNT_TESTING 604 605 #define COEF_COUNT_SAT 24 606 #define COEF_MAX_UPDATE_FACTOR 112 607 #define COEF_COUNT_SAT_KEY 24 608 #define COEF_MAX_UPDATE_FACTOR_KEY 112 609 #define COEF_COUNT_SAT_AFTER_KEY 24 610 #define COEF_MAX_UPDATE_FACTOR_AFTER_KEY 128 611 612 static void adapt_coef_probs(VP9_COMMON *cm, TX_SIZE tx_size, 613 unsigned int count_sat, 614 unsigned int update_factor) { 615 FRAME_CONTEXT *pre_fc = &cm->frame_contexts[cm->frame_context_idx]; 616 617 vp9_coeff_probs_model *dst_coef_probs = cm->fc.coef_probs[tx_size]; 618 vp9_coeff_probs_model *pre_coef_probs = pre_fc->coef_probs[tx_size]; 619 vp9_coeff_count_model *coef_counts = cm->counts.coef[tx_size]; 620 unsigned int (*eob_branch_count)[REF_TYPES][COEF_BANDS][PREV_COEF_CONTEXTS] = 621 cm->counts.eob_branch[tx_size]; 622 int t, i, j, k, l; 623 unsigned int branch_ct[UNCONSTRAINED_NODES][2]; 624 vp9_prob coef_probs[UNCONSTRAINED_NODES]; 625 626 for (i = 0; i < BLOCK_TYPES; ++i) 627 for (j = 0; j < REF_TYPES; ++j) 628 for (k = 0; k < COEF_BANDS; ++k) 629 for (l = 0; l < PREV_COEF_CONTEXTS; ++l) { 630 if (l >= 3 && k == 0) 631 continue; 632 vp9_tree_probs_from_distribution(vp9_coefmodel_tree, coef_probs, 633 branch_ct, coef_counts[i][j][k][l], 634 0); 635 branch_ct[0][1] = eob_branch_count[i][j][k][l] - branch_ct[0][0]; 636 coef_probs[0] = get_binary_prob(branch_ct[0][0], branch_ct[0][1]); 637 for (t = 0; t < UNCONSTRAINED_NODES; ++t) 638 dst_coef_probs[i][j][k][l][t] = merge_probs( 639 pre_coef_probs[i][j][k][l][t], coef_probs[t], 640 branch_ct[t], count_sat, update_factor); 641 } 642 } 643 644 void vp9_adapt_coef_probs(VP9_COMMON *cm) { 645 TX_SIZE t; 646 unsigned int count_sat, update_factor; 647 648 if (cm->frame_type == KEY_FRAME || cm->intra_only) { 649 update_factor = COEF_MAX_UPDATE_FACTOR_KEY; 650 count_sat = COEF_COUNT_SAT_KEY; 651 } else if (cm->last_frame_type == KEY_FRAME) { 652 update_factor = COEF_MAX_UPDATE_FACTOR_AFTER_KEY; /* adapt quickly */ 653 count_sat = COEF_COUNT_SAT_AFTER_KEY; 654 } else { 655 update_factor = COEF_MAX_UPDATE_FACTOR; 656 count_sat = COEF_COUNT_SAT; 657 } 658 for (t = TX_4X4; t <= TX_32X32; t++) 659 adapt_coef_probs(cm, t, count_sat, update_factor); 660 } 661
