media/dvb-core/dvb_math.c

0001 /*
0002  * dvb-math provides some complex fixed-point math
0003  * operations shared between the dvb related stuff
0004  *
0005  * Copyright (C) 2006 Christoph Pfister (christophpfister@gmail.com)
0006  *
0007  * This library is free software; you can redistribute it and/or modify
0008  * it under the terms of the GNU Lesser General Public License as
0009  * published by the Free Software Foundation; either version 2.1 of
0010  * the License, or (at your option) any later version.
0011  *
0012  * This program is distributed in the hope that it will be useful,
0013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
0014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
0015  * GNU Lesser General Public License for more details.
0016  */
0017
0018 #include <linux/bitops.h>
0019 #include <linux/kernel.h>
0020 #include <linux/module.h>
0021 #include <asm/bug.h>
0022 #include <media/dvb_math.h>
0023
0024 static const unsigned short logtable[256] = {
0025     0x0000, 0x0171, 0x02e0, 0x044e, 0x05ba, 0x0725, 0x088e, 0x09f7,
0026     0x0b5d, 0x0cc3, 0x0e27, 0x0f8a, 0x10eb, 0x124b, 0x13aa, 0x1508,
0027     0x1664, 0x17bf, 0x1919, 0x1a71, 0x1bc8, 0x1d1e, 0x1e73, 0x1fc6,
0028     0x2119, 0x226a, 0x23ba, 0x2508, 0x2656, 0x27a2, 0x28ed, 0x2a37,
0029     0x2b80, 0x2cc8, 0x2e0f, 0x2f54, 0x3098, 0x31dc, 0x331e, 0x345f,
0030     0x359f, 0x36de, 0x381b, 0x3958, 0x3a94, 0x3bce, 0x3d08, 0x3e41,
0031     0x3f78, 0x40af, 0x41e4, 0x4319, 0x444c, 0x457f, 0x46b0, 0x47e1,
0032     0x4910, 0x4a3f, 0x4b6c, 0x4c99, 0x4dc5, 0x4eef, 0x5019, 0x5142,
0033     0x526a, 0x5391, 0x54b7, 0x55dc, 0x5700, 0x5824, 0x5946, 0x5a68,
0034     0x5b89, 0x5ca8, 0x5dc7, 0x5ee5, 0x6003, 0x611f, 0x623a, 0x6355,
0035     0x646f, 0x6588, 0x66a0, 0x67b7, 0x68ce, 0x69e4, 0x6af8, 0x6c0c,
0036     0x6d20, 0x6e32, 0x6f44, 0x7055, 0x7165, 0x7274, 0x7383, 0x7490,
0037     0x759d, 0x76aa, 0x77b5, 0x78c0, 0x79ca, 0x7ad3, 0x7bdb, 0x7ce3,
0038     0x7dea, 0x7ef0, 0x7ff6, 0x80fb, 0x81ff, 0x8302, 0x8405, 0x8507,
0039     0x8608, 0x8709, 0x8809, 0x8908, 0x8a06, 0x8b04, 0x8c01, 0x8cfe,
0040     0x8dfa, 0x8ef5, 0x8fef, 0x90e9, 0x91e2, 0x92db, 0x93d2, 0x94ca,
0041     0x95c0, 0x96b6, 0x97ab, 0x98a0, 0x9994, 0x9a87, 0x9b7a, 0x9c6c,
0042     0x9d5e, 0x9e4f, 0x9f3f, 0xa02e, 0xa11e, 0xa20c, 0xa2fa, 0xa3e7,
0043     0xa4d4, 0xa5c0, 0xa6ab, 0xa796, 0xa881, 0xa96a, 0xaa53, 0xab3c,
0044     0xac24, 0xad0c, 0xadf2, 0xaed9, 0xafbe, 0xb0a4, 0xb188, 0xb26c,
0045     0xb350, 0xb433, 0xb515, 0xb5f7, 0xb6d9, 0xb7ba, 0xb89a, 0xb97a,
0046     0xba59, 0xbb38, 0xbc16, 0xbcf4, 0xbdd1, 0xbead, 0xbf8a, 0xc065,
0047     0xc140, 0xc21b, 0xc2f5, 0xc3cf, 0xc4a8, 0xc580, 0xc658, 0xc730,
0048     0xc807, 0xc8de, 0xc9b4, 0xca8a, 0xcb5f, 0xcc34, 0xcd08, 0xcddc,
0049     0xceaf, 0xcf82, 0xd054, 0xd126, 0xd1f7, 0xd2c8, 0xd399, 0xd469,
0050     0xd538, 0xd607, 0xd6d6, 0xd7a4, 0xd872, 0xd93f, 0xda0c, 0xdad9,
0051     0xdba5, 0xdc70, 0xdd3b, 0xde06, 0xded0, 0xdf9a, 0xe063, 0xe12c,
0052     0xe1f5, 0xe2bd, 0xe385, 0xe44c, 0xe513, 0xe5d9, 0xe69f, 0xe765,
0053     0xe82a, 0xe8ef, 0xe9b3, 0xea77, 0xeb3b, 0xebfe, 0xecc1, 0xed83,
0054     0xee45, 0xef06, 0xefc8, 0xf088, 0xf149, 0xf209, 0xf2c8, 0xf387,
0055     0xf446, 0xf505, 0xf5c3, 0xf680, 0xf73e, 0xf7fb, 0xf8b7, 0xf973,
0056     0xfa2f, 0xfaea, 0xfba5, 0xfc60, 0xfd1a, 0xfdd4, 0xfe8e, 0xff47
0057 };
0058
0059 unsigned int intlog2(u32 value)
0060 {
0061     /**
0062      *  returns: log2(value) * 2^24
0063      *  wrong result if value = 0 (log2(0) is undefined)
0064      */
0065     unsigned int msb;
0066     unsigned int logentry;
0067     unsigned int significand;
0068     unsigned int interpolation;
0069
0070     if (unlikely(value == 0)) {
0071         WARN_ON(1);
0072         return 0;
0073     }
0074
0075     /* first detect the msb (count begins at 0) */
0076     msb = fls(value) - 1;
0077
0078     /**
0079      *  now we use a logtable after the following method:
0080      *
0081      *  log2(2^x * y) * 2^24 = x * 2^24 + log2(y) * 2^24
0082      *  where x = msb and therefore 1 <= y < 2
0083      *  first y is determined by shifting the value left
0084      *  so that msb is bit 31
0085      *      0x00231f56 -> 0x8C7D5800
0086      *  the result is y * 2^31 -> "significand"
0087      *  then the highest 9 bits are used for a table lookup
0088      *  the highest bit is discarded because it's always set
0089      *  the highest nine bits in our example are 100011000
0090      *  so we would use the entry 0x18
0091      */
0092     significand = value << (31 - msb);
0093     logentry = (significand >> 23) & 0xff;
0094
0095     /**
0096      *  last step we do is interpolation because of the
0097      *  limitations of the log table the error is that part of
0098      *  the significand which isn't used for lookup then we
0099      *  compute the ratio between the error and the next table entry
0100      *  and interpolate it between the log table entry used and the
0101      *  next one the biggest error possible is 0x7fffff
0102      *  (in our example it's 0x7D5800)
0103      *  needed value for next table entry is 0x800000
0104      *  so the interpolation is
0105      *  (error / 0x800000) * (logtable_next - logtable_current)
0106      *  in the implementation the division is moved to the end for
0107      *  better accuracy there is also an overflow correction if
0108      *  logtable_next is 256
0109      */
0110     interpolation = ((significand & 0x7fffff) *
0111             ((logtable[(logentry + 1) & 0xff] -
0112               logtable[logentry]) & 0xffff)) >> 15;
0113
0114     /* now we return the result */
0115     return ((msb << 24) + (logtable[logentry] << 8) + interpolation);
0116 }
0117 EXPORT_SYMBOL(intlog2);
0118
0119 unsigned int intlog10(u32 value)
0120 {
0121     /**
0122      *  returns: log10(value) * 2^24
0123      *  wrong result if value = 0 (log10(0) is undefined)
0124      */
0125     u64 log;
0126
0127     if (unlikely(value == 0)) {
0128         WARN_ON(1);
0129         return 0;
0130     }
0131
0132     log = intlog2(value);
0133
0134     /**
0135      *  we use the following method:
0136      *  log10(x) = log2(x) * log10(2)
0137      */
0138
0139     return (log * 646456993) >> 31;
0140 }
0141 EXPORT_SYMBOL(intlog10);