ffmpeg/libavcodec/mathtables.c

   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 #include "mathops.h"
  24
  25 /* a*inverse[b]>>32 == a/b for all 0<=a<=16909558 && 2<=b<=256
  26  * for a>16909558, is an overestimate by less than 1 part in 1<<24 */
  27 const uint32_t ff_inverse[257]={
  28          0, 4294967295U,2147483648U,1431655766, 1073741824,  858993460,  715827883,  613566757,
  29  536870912,  477218589,  429496730,  390451573,  357913942,  330382100,  306783379,  286331154,
  30  268435456,  252645136,  238609295,  226050911,  214748365,  204522253,  195225787,  186737709,
  31  178956971,  171798692,  165191050,  159072863,  153391690,  148102321,  143165577,  138547333,
  32  134217728,  130150525,  126322568,  122713352,  119304648,  116080198,  113025456,  110127367,
  33  107374183,  104755300,  102261127,   99882961,   97612894,   95443718,   93368855,   91382283,
  34   89478486,   87652394,   85899346,   84215046,   82595525,   81037119,   79536432,   78090315,
  35   76695845,   75350304,   74051161,   72796056,   71582789,   70409300,   69273667,   68174085,
  36   67108864,   66076420,   65075263,   64103990,   63161284,   62245903,   61356676,   60492498,
  37   59652324,   58835169,   58040099,   57266231,   56512728,   55778797,   55063684,   54366675,
  38   53687092,   53024288,   52377650,   51746594,   51130564,   50529028,   49941481,   49367441,
  39   48806447,   48258060,   47721859,   47197443,   46684428,   46182445,   45691142,   45210183,
  40   44739243,   44278014,   43826197,   43383509,   42949673,   42524429,   42107523,   41698712,
  41   41297763,   40904451,   40518560,   40139882,   39768216,   39403370,   39045158,   38693400,
  42   38347923,   38008561,   37675152,   37347542,   37025581,   36709123,   36398028,   36092163,
  43   35791395,   35495598,   35204650,   34918434,   34636834,   34359739,   34087043,   33818641,
  44   33554432,   33294321,   33038210,   32786010,   32537632,   32292988,   32051995,   31814573,
  45   31580642,   31350127,   31122952,   30899046,   30678338,   30460761,   30246249,   30034737,
  46   29826162,   29620465,   29417585,   29217465,   29020050,   28825284,   28633116,   28443493,
  47   28256364,   28071682,   27889399,   27709467,   27531842,   27356480,   27183338,   27012373,
  48   26843546,   26676816,   26512144,   26349493,   26188825,   26030105,   25873297,   25718368,
  49   25565282,   25414008,   25264514,   25116768,   24970741,   24826401,   24683721,   24542671,
  50   24403224,   24265352,   24129030,   23994231,   23860930,   23729102,   23598722,   23469767,
  51   23342214,   23216040,   23091223,   22967740,   22845571,   22724695,   22605092,   22486740,
  52   22369622,   22253717,   22139007,   22025474,   21913099,   21801865,   21691755,   21582751,
  53   21474837,   21367997,   21262215,   21157475,   21053762,   20951060,   20849356,   20748635,
  54   20648882,   20550083,   20452226,   20355296,   20259280,   20164166,   20069941,   19976593,
  55   19884108,   19792477,   19701685,   19611723,   19522579,   19434242,   19346700,   19259944,
  56   19173962,   19088744,   19004281,   18920561,   18837576,   18755316,   18673771,   18592933,
  57   18512791,   18433337,   18354562,   18276457,   18199014,   18122225,   18046082,   17970575,
  58   17895698,   17821442,   17747799,   17674763,   17602325,   17530479,   17459217,   17388532,
  59   17318417,   17248865,   17179870,   17111424,   17043522,   16976156,   16909321,   16843010,
  60   16777216
  61 };
  62
  63 const uint8_t ff_sqrt_tab[256]={
  64   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,
  65  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,
  66 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,
  67 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,
  68 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,
  69 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,
  70 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,
  71 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
  72 };
  73
  74 const uint8_t ff_reverse[256] = {
  75 0x00,0x80,0x40,0xC0,0x20,0xA0,0x60,0xE0,0x10,0x90,0x50,0xD0,0x30,0xB0,0x70,0xF0,
  76 0x08,0x88,0x48,0xC8,0x28,0xA8,0x68,0xE8,0x18,0x98,0x58,0xD8,0x38,0xB8,0x78,0xF8,
  77 0x04,0x84,0x44,0xC4,0x24,0xA4,0x64,0xE4,0x14,0x94,0x54,0xD4,0x34,0xB4,0x74,0xF4,
  78 0x0C,0x8C,0x4C,0xCC,0x2C,0xAC,0x6C,0xEC,0x1C,0x9C,0x5C,0xDC,0x3C,0xBC,0x7C,0xFC,
  79 0x02,0x82,0x42,0xC2,0x22,0xA2,0x62,0xE2,0x12,0x92,0x52,0xD2,0x32,0xB2,0x72,0xF2,
  80 0x0A,0x8A,0x4A,0xCA,0x2A,0xAA,0x6A,0xEA,0x1A,0x9A,0x5A,0xDA,0x3A,0xBA,0x7A,0xFA,
  81 0x06,0x86,0x46,0xC6,0x26,0xA6,0x66,0xE6,0x16,0x96,0x56,0xD6,0x36,0xB6,0x76,0xF6,
  82 0x0E,0x8E,0x4E,0xCE,0x2E,0xAE,0x6E,0xEE,0x1E,0x9E,0x5E,0xDE,0x3E,0xBE,0x7E,0xFE,
  83 0x01,0x81,0x41,0xC1,0x21,0xA1,0x61,0xE1,0x11,0x91,0x51,0xD1,0x31,0xB1,0x71,0xF1,
  84 0x09,0x89,0x49,0xC9,0x29,0xA9,0x69,0xE9,0x19,0x99,0x59,0xD9,0x39,0xB9,0x79,0xF9,
  85 0x05,0x85,0x45,0xC5,0x25,0xA5,0x65,0xE5,0x15,0x95,0x55,0xD5,0x35,0xB5,0x75,0xF5,
  86 0x0D,0x8D,0x4D,0xCD,0x2D,0xAD,0x6D,0xED,0x1D,0x9D,0x5D,0xDD,0x3D,0xBD,0x7D,0xFD,
  87 0x03,0x83,0x43,0xC3,0x23,0xA3,0x63,0xE3,0x13,0x93,0x53,0xD3,0x33,0xB3,0x73,0xF3,
  88 0x0B,0x8B,0x4B,0xCB,0x2B,0xAB,0x6B,0xEB,0x1B,0x9B,0x5B,0xDB,0x3B,0xBB,0x7B,0xFB,
  89 0x07,0x87,0x47,0xC7,0x27,0xA7,0x67,0xE7,0x17,0x97,0x57,0xD7,0x37,0xB7,0x77,0xF7,
  90 0x0F,0x8F,0x4F,0xCF,0x2F,0xAF,0x6F,0xEF,0x1F,0x9F,0x5F,0xDF,0x3F,0xBF,0x7F,0xFF,
  91 };
  92
  93 #define times4(x) x, x, x, x
  94 #define times256(x) times4(times4(times4(times4(times4(x)))))
  95
  96 const uint8_t ff_crop_tab[256 + 2 * MAX_NEG_CROP] = {
  97 times256(0x00),
  98 0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0A,0x0B,0x0C,0x0D,0x0E,0x0F,
  99 0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17,0x18,0x19,0x1A,0x1B,0x1C,0x1D,0x1E,0x1F,
 100 0x20,0x21,0x22,0x23,0x24,0x25,0x26,0x27,0x28,0x29,0x2A,0x2B,0x2C,0x2D,0x2E,0x2F,
 101 0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37,0x38,0x39,0x3A,0x3B,0x3C,0x3D,0x3E,0x3F,
 102 0x40,0x41,0x42,0x43,0x44,0x45,0x46,0x47,0x48,0x49,0x4A,0x4B,0x4C,0x4D,0x4E,0x4F,
 103 0x50,0x51,0x52,0x53,0x54,0x55,0x56,0x57,0x58,0x59,0x5A,0x5B,0x5C,0x5D,0x5E,0x5F,
 104 0x60,0x61,0x62,0x63,0x64,0x65,0x66,0x67,0x68,0x69,0x6A,0x6B,0x6C,0x6D,0x6E,0x6F,
 105 0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77,0x78,0x79,0x7A,0x7B,0x7C,0x7D,0x7E,0x7F,
 106 0x80,0x81,0x82,0x83,0x84,0x85,0x86,0x87,0x88,0x89,0x8A,0x8B,0x8C,0x8D,0x8E,0x8F,
 107 0x90,0x91,0x92,0x93,0x94,0x95,0x96,0x97,0x98,0x99,0x9A,0x9B,0x9C,0x9D,0x9E,0x9F,
 108 0xA0,0xA1,0xA2,0xA3,0xA4,0xA5,0xA6,0xA7,0xA8,0xA9,0xAA,0xAB,0xAC,0xAD,0xAE,0xAF,
 109 0xB0,0xB1,0xB2,0xB3,0xB4,0xB5,0xB6,0xB7,0xB8,0xB9,0xBA,0xBB,0xBC,0xBD,0xBE,0xBF,
 110 0xC0,0xC1,0xC2,0xC3,0xC4,0xC5,0xC6,0xC7,0xC8,0xC9,0xCA,0xCB,0xCC,0xCD,0xCE,0xCF,
 111 0xD0,0xD1,0xD2,0xD3,0xD4,0xD5,0xD6,0xD7,0xD8,0xD9,0xDA,0xDB,0xDC,0xDD,0xDE,0xDF,
 112 0xE0,0xE1,0xE2,0xE3,0xE4,0xE5,0xE6,0xE7,0xE8,0xE9,0xEA,0xEB,0xEC,0xED,0xEE,0xEF,
 113 0xF0,0xF1,0xF2,0xF3,0xF4,0xF5,0xF6,0xF7,0xF8,0xF9,0xFA,0xFB,0xFC,0xFD,0xFE,0xFF,
 114 times256(0xFF)
 115 };
 116
 117 const uint8_t ff_zigzag_direct[64] = {
 118     0,   1,  8, 16,  9,  2,  3, 10,
 119     17, 24, 32, 25, 18, 11,  4,  5,
 120     12, 19, 26, 33, 40, 48, 41, 34,
 121     27, 20, 13,  6,  7, 14, 21, 28,
 122     35, 42, 49, 56, 57, 50, 43, 36,
 123     29, 22, 15, 23, 30, 37, 44, 51,
 124     58, 59, 52, 45, 38, 31, 39, 46,
 125     53, 60, 61, 54, 47, 55, 62, 63
 126 };