1 /*
2 * Copyright (c) 2002-2004 Michael Niedermayer <michaelni@gmx.at>
3 *
4 * This file is part of FFmpeg.
5 *
6 * FFmpeg is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2.1 of the License, or (at your option) any later version.
10 *
11 * FFmpeg is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with FFmpeg; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19 */
20
21 #include <stdint.h>
22
23 /* a*inverse[b]>>32 == a/b for all 0<=a<=16909558 && 2<=b<=256
24 * for a>16909558, is an overestimate by less than 1 part in 1<<24 */
26 0, 4294967295
U,2147483648
U,1431655766, 1073741824, 858993460, 715827883, 613566757,
27 536870912, 477218589, 429496730, 390451573, 357913942, 330382100, 306783379, 286331154,
28 268435456, 252645136, 238609295, 226050911, 214748365, 204522253, 195225787, 186737709,
29 178956971, 171798692, 165191050, 159072863, 153391690, 148102321, 143165577, 138547333,
30 134217728, 130150525, 126322568, 122713352, 119304648, 116080198, 113025456, 110127367,
31 107374183, 104755300, 102261127, 99882961, 97612894, 95443718, 93368855, 91382283,
32 89478486, 87652394, 85899346, 84215046, 82595525, 81037119, 79536432, 78090315,
33 76695845, 75350304, 74051161, 72796056, 71582789, 70409300, 69273667, 68174085,
34 67108864, 66076420, 65075263, 64103990, 63161284, 62245903, 61356676, 60492498,
35 59652324, 58835169, 58040099, 57266231, 56512728, 55778797, 55063684, 54366675,
36 53687092, 53024288, 52377650, 51746594, 51130564, 50529028, 49941481, 49367441,
37 48806447, 48258060, 47721859, 47197443, 46684428, 46182445, 45691142, 45210183,
38 44739243, 44278014, 43826197, 43383509, 42949673, 42524429, 42107523, 41698712,
39 41297763, 40904451, 40518560, 40139882, 39768216, 39403370, 39045158, 38693400,
40 38347923, 38008561, 37675152, 37347542, 37025581, 36709123, 36398028, 36092163,
41 35791395, 35495598, 35204650, 34918434, 34636834, 34359739, 34087043, 33818641,
42 33554432, 33294321, 33038210, 32786010, 32537632, 32292988, 32051995, 31814573,
43 31580642, 31350127, 31122952, 30899046, 30678338, 30460761, 30246249, 30034737,
44 29826162, 29620465, 29417585, 29217465, 29020050, 28825284, 28633116, 28443493,
45 28256364, 28071682, 27889399, 27709467, 27531842, 27356480, 27183338, 27012373,
46 26843546, 26676816, 26512144, 26349493, 26188825, 26030105, 25873297, 25718368,
47 25565282, 25414008, 25264514, 25116768, 24970741, 24826401, 24683721, 24542671,
48 24403224, 24265352, 24129030, 23994231, 23860930, 23729102, 23598722, 23469767,
49 23342214, 23216040, 23091223, 22967740, 22845571, 22724695, 22605092, 22486740,
50 22369622, 22253717, 22139007, 22025474, 21913099, 21801865, 21691755, 21582751,
51 21474837, 21367997, 21262215, 21157475, 21053762, 20951060, 20849356, 20748635,
52 20648882, 20550083, 20452226, 20355296, 20259280, 20164166, 20069941, 19976593,
53 19884108, 19792477, 19701685, 19611723, 19522579, 19434242, 19346700, 19259944,
54 19173962, 19088744, 19004281, 18920561, 18837576, 18755316, 18673771, 18592933,
55 18512791, 18433337, 18354562, 18276457, 18199014, 18122225, 18046082, 17970575,
56 17895698, 17821442, 17747799, 17674763, 17602325, 17530479, 17459217, 17388532,
57 17318417, 17248865, 17179870, 17111424, 17043522, 16976156, 16909321, 16843010,
58 16777216
59 };
60
62 0, 16, 23, 28, 32, 36, 40, 43, 46, 48, 51, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 77, 79, 80, 82, 84, 85, 87, 88, 90,
63 91, 92, 94, 95, 96, 98, 99,100,102,103,104,105,107,108,109,110,111,112,114,115,116,117,118,119,120,121,122,123,124,125,126,127,
64 128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,144,145,146,147,148,149,150,151,151,152,153,154,155,156,156,
65 157,158,159,160,160,161,162,163,164,164,165,166,167,168,168,169,170,171,171,172,173,174,174,175,176,176,177,178,179,179,180,181,
66 182,182,183,184,184,185,186,186,187,188,188,189,190,190,191,192,192,193,194,194,195,196,196,197,198,198,199,200,200,201,202,202,
67 203,204,204,205,205,206,207,207,208,208,209,210,210,211,212,212,213,213,214,215,215,216,216,217,218,218,219,219,220,220,221,222,
68 222,223,223,224,224,225,226,226,227,227,228,228,229,230,230,231,231,232,232,233,233,234,235,235,236,236,237,237,238,238,239,239,
69 240,240,241,242,242,243,243,244,244,245,245,246,246,247,247,248,248,249,249,250,250,251,251,252,252,253,253,254,254,255,255,255
70 };
71
73 0x00,0x80,0x40,0xC0,0x20,0xA0,0x60,0xE0,0x10,0x90,0x50,0xD0,0x30,0xB0,0x70,0xF0,
74 0x08,0x88,0x48,0xC8,0x28,0xA8,0x68,0xE8,0x18,0x98,0x58,0xD8,0x38,0xB8,0x78,0xF8,
75 0x04,0x84,0x44,0xC4,0x24,0xA4,0x64,0xE4,0x14,0x94,0x54,0xD4,0x34,0xB4,0x74,0xF4,
76 0x0C,0x8C,0x4C,0xCC,0x2C,0xAC,0x6C,0xEC,0x1C,0x9C,0x5C,0xDC,0x3C,0xBC,0x7C,0xFC,
77 0x02,0x82,0x42,0xC2,0x22,0xA2,0x62,0xE2,0x12,0x92,0x52,0xD2,0x32,0xB2,0x72,0xF2,
78 0x0A,0x8A,0x4A,0xCA,0x2A,0xAA,0x6A,0xEA,0x1A,0x9A,0x5A,0xDA,0x3A,0xBA,0x7A,0xFA,
79 0x06,0x86,0x46,0xC6,0x26,0xA6,0x66,0xE6,0x16,0x96,0x56,0xD6,0x36,0xB6,0x76,0xF6,
80 0x0E,0x8E,0x4E,0xCE,0x2E,0xAE,0x6E,0xEE,0x1E,0x9E,0x5E,0xDE,0x3E,0xBE,0x7E,0xFE,
81 0x01,0x81,0x41,0xC1,0x21,0xA1,0x61,0xE1,0x11,0x91,0x51,0xD1,0x31,0xB1,0x71,0xF1,
82 0x09,0x89,0x49,0xC9,0x29,0xA9,0x69,0xE9,0x19,0x99,0x59,0xD9,0x39,0xB9,0x79,0xF9,
83 0x05,0x85,0x45,0xC5,0x25,0xA5,0x65,0xE5,0x15,0x95,0x55,0xD5,0x35,0xB5,0x75,0xF5,
84 0x0D,0x8D,0x4D,0xCD,0x2D,0xAD,0x6D,0xED,0x1D,0x9D,0x5D,0xDD,0x3D,0xBD,0x7D,0xFD,
85 0x03,0x83,0x43,0xC3,0x23,0xA3,0x63,0xE3,0x13,0x93,0x53,0xD3,0x33,0xB3,0x73,0xF3,
86 0x0B,0x8B,0x4B,0xCB,0x2B,0xAB,0x6B,0xEB,0x1B,0x9B,0x5B,0xDB,0x3B,0xBB,0x7B,0xFB,
87 0x07,0x87,0x47,0xC7,0x27,0xA7,0x67,0xE7,0x17,0x97,0x57,0xD7,0x37,0xB7,0x77,0xF7,
88 0x0F,0x8F,0x4F,0xCF,0x2F,0xAF,0x6F,0xEF,0x1F,0x9F,0x5F,0xDF,0x3F,0xBF,0x7F,0xFF,
89 };
90
91 #define times4(x) x, x, x, x
92 #define times256(x) times4(times4(times4(times4(times4(x)))))
93
96 0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0A,0x0B,0x0C,0x0D,0x0E,0x0F,
97 0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17,0x18,0x19,0x1A,0x1B,0x1C,0x1D,0x1E,0x1F,
98 0x20,0x21,0x22,0x23,0x24,0x25,0x26,0x27,0x28,0x29,0x2A,0x2B,0x2C,0x2D,0x2E,0x2F,
99 0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37,0x38,0x39,0x3A,0x3B,0x3C,0x3D,0x3E,0x3F,
100 0x40,0x41,0x42,0x43,0x44,0x45,0x46,0x47,0x48,0x49,0x4A,0x4B,0x4C,0x4D,0x4E,0x4F,
101 0x50,0x51,0x52,0x53,0x54,0x55,0x56,0x57,0x58,0x59,0x5A,0x5B,0x5C,0x5D,0x5E,0x5F,
102 0x60,0x61,0x62,0x63,0x64,0x65,0x66,0x67,0x68,0x69,0x6A,0x6B,0x6C,0x6D,0x6E,0x6F,
103 0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77,0x78,0x79,0x7A,0x7B,0x7C,0x7D,0x7E,0x7F,
104 0x80,0x81,0x82,0x83,0x84,0x85,0x86,0x87,0x88,0x89,0x8A,0x8B,0x8C,0x8D,0x8E,0x8F,
105 0x90,0x91,0x92,0x93,0x94,0x95,0x96,0x97,0x98,0x99,0x9A,0x9B,0x9C,0x9D,0x9E,0x9F,
106 0xA0,0xA1,0xA2,0xA3,0xA4,0xA5,0xA6,0xA7,0xA8,0xA9,0xAA,0xAB,0xAC,0xAD,0xAE,0xAF,
107 0xB0,0xB1,0xB2,0xB3,0xB4,0xB5,0xB6,0xB7,0xB8,0xB9,0xBA,0xBB,0xBC,0xBD,0xBE,0xBF,
108 0xC0,0xC1,0xC2,0xC3,0xC4,0xC5,0xC6,0xC7,0xC8,0xC9,0xCA,0xCB,0xCC,0xCD,0xCE,0xCF,
109 0xD0,0xD1,0xD2,0xD3,0xD4,0xD5,0xD6,0xD7,0xD8,0xD9,0xDA,0xDB,0xDC,0xDD,0xDE,0xDF,
110 0xE0,0xE1,0xE2,0xE3,0xE4,0xE5,0xE6,0xE7,0xE8,0xE9,0xEA,0xEB,0xEC,0xED,0xEE,0xEF,
111 0xF0,0xF1,0xF2,0xF3,0xF4,0xF5,0xF6,0xF7,0xF8,0xF9,0xFA,0xFB,0xFC,0xFD,0xFE,0xFF,
113 };
114
116 0, 1, 8, 16, 9, 2, 3, 10,
117 17, 24, 32, 25, 18, 11, 4, 5,
118 12, 19, 26, 33, 40, 48, 41, 34,
119 27, 20, 13, 6, 7, 14, 21, 28,
120 35, 42, 49, 56, 57, 50, 43, 36,
121 29, 22, 15, 23, 30, 37, 44, 51,
122 58, 59, 52, 45, 38, 31, 39, 46,
123 53, 60, 61, 54, 47, 55, 62, 63
124 };