diff options
author | Wolfgang Wiedmeyer <wolfgit@wiedmeyer.de> | 2015-10-23 03:29:33 +0200 |
---|---|---|
committer | Wolfgang Wiedmeyer <wolfgit@wiedmeyer.de> | 2015-10-23 03:29:33 +0200 |
commit | 15dfd0df63ce6847081d09b2bbd567cc0cc4eae1 (patch) | |
tree | 3b73f24fcef970bfcace3cbb297cfa57f3994682 /lib | |
parent | 328aa7a45af61bc0060c80847daa67fef7b9c0d0 (diff) | |
parent | 0149138c4142da287d23f9d5c6038f7fb5e30ac2 (diff) | |
download | kernel_samsung_smdk4412-15dfd0df63ce6847081d09b2bbd567cc0cc4eae1.zip kernel_samsung_smdk4412-15dfd0df63ce6847081d09b2bbd567cc0cc4eae1.tar.gz kernel_samsung_smdk4412-15dfd0df63ce6847081d09b2bbd567cc0cc4eae1.tar.bz2 |
initial merge with 3.2.72
Diffstat (limited to 'lib')
-rw-r--r-- | lib/cordic.c | 101 | ||||
-rw-r--r-- | lib/crc8.c | 86 | ||||
-rw-r--r-- | lib/kstrtox.h | 8 | ||||
-rw-r--r-- | lib/llist.c | 89 | ||||
-rw-r--r-- | lib/lzo/lzo1x_decompress_safe.c | 268 |
5 files changed, 552 insertions, 0 deletions
diff --git a/lib/cordic.c b/lib/cordic.c new file mode 100644 index 0000000..aa27a88 --- /dev/null +++ b/lib/cordic.c @@ -0,0 +1,101 @@ +/* + * Copyright (c) 2011 Broadcom Corporation + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY + * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION + * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN + * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ +#include <linux/module.h> +#include <linux/cordic.h> + +#define CORDIC_ANGLE_GEN 39797 +#define CORDIC_PRECISION_SHIFT 16 +#define CORDIC_NUM_ITER (CORDIC_PRECISION_SHIFT + 2) + +#define FIXED(X) ((s32)((X) << CORDIC_PRECISION_SHIFT)) +#define FLOAT(X) (((X) >= 0) \ + ? ((((X) >> (CORDIC_PRECISION_SHIFT - 1)) + 1) >> 1) \ + : -((((-(X)) >> (CORDIC_PRECISION_SHIFT - 1)) + 1) >> 1)) + +static const s32 arctan_table[] = { + 2949120, + 1740967, + 919879, + 466945, + 234379, + 117304, + 58666, + 29335, + 14668, + 7334, + 3667, + 1833, + 917, + 458, + 229, + 115, + 57, + 29 +}; + +/* + * cordic_calc_iq() - calculates the i/q coordinate for given angle + * + * theta: angle in degrees for which i/q coordinate is to be calculated + * coord: function output parameter holding the i/q coordinate + */ +struct cordic_iq cordic_calc_iq(s32 theta) +{ + struct cordic_iq coord; + s32 angle, valtmp; + unsigned iter; + int signx = 1; + int signtheta; + + coord.i = CORDIC_ANGLE_GEN; + coord.q = 0; + angle = 0; + + theta = FIXED(theta); + signtheta = (theta < 0) ? -1 : 1; + theta = ((theta + FIXED(180) * signtheta) % FIXED(360)) - + FIXED(180) * signtheta; + + if (FLOAT(theta) > 90) { + theta -= FIXED(180); + signx = -1; + } else if (FLOAT(theta) < -90) { + theta += FIXED(180); + signx = -1; + } + + for (iter = 0; iter < CORDIC_NUM_ITER; iter++) { + if (theta > angle) { + valtmp = coord.i - (coord.q >> iter); + coord.q += (coord.i >> iter); + angle += arctan_table[iter]; + } else { + valtmp = coord.i + (coord.q >> iter); + coord.q -= (coord.i >> iter); + angle -= arctan_table[iter]; + } + coord.i = valtmp; + } + + coord.i *= signx; + coord.q *= signx; + return coord; +} +EXPORT_SYMBOL(cordic_calc_iq); + +MODULE_DESCRIPTION("Cordic functions"); +MODULE_AUTHOR("Broadcom Corporation"); +MODULE_LICENSE("Dual BSD/GPL"); diff --git a/lib/crc8.c b/lib/crc8.c new file mode 100644 index 0000000..87b59ca --- /dev/null +++ b/lib/crc8.c @@ -0,0 +1,86 @@ +/* + * Copyright (c) 2011 Broadcom Corporation + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY + * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION + * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN + * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt + +#include <linux/module.h> +#include <linux/crc8.h> +#include <linux/printk.h> + +/* + * crc8_populate_msb - fill crc table for given polynomial in reverse bit order. + * + * table: table to be filled. + * polynomial: polynomial for which table is to be filled. + */ +void crc8_populate_msb(u8 table[CRC8_TABLE_SIZE], u8 polynomial) +{ + int i, j; + const u8 msbit = 0x80; + u8 t = msbit; + + table[0] = 0; + + for (i = 1; i < CRC8_TABLE_SIZE; i *= 2) { + t = (t << 1) ^ (t & msbit ? polynomial : 0); + for (j = 0; j < i; j++) + table[i+j] = table[j] ^ t; + } +} +EXPORT_SYMBOL(crc8_populate_msb); + +/* + * crc8_populate_lsb - fill crc table for given polynomial in regular bit order. + * + * table: table to be filled. + * polynomial: polynomial for which table is to be filled. + */ +void crc8_populate_lsb(u8 table[CRC8_TABLE_SIZE], u8 polynomial) +{ + int i, j; + u8 t = 1; + + table[0] = 0; + + for (i = (CRC8_TABLE_SIZE >> 1); i; i >>= 1) { + t = (t >> 1) ^ (t & 1 ? polynomial : 0); + for (j = 0; j < CRC8_TABLE_SIZE; j += 2*i) + table[i+j] = table[j] ^ t; + } +} +EXPORT_SYMBOL(crc8_populate_lsb); + +/* + * crc8 - calculate a crc8 over the given input data. + * + * table: crc table used for calculation. + * pdata: pointer to data buffer. + * nbytes: number of bytes in data buffer. + * crc: previous returned crc8 value. + */ +u8 crc8(const u8 table[CRC8_TABLE_SIZE], u8 *pdata, size_t nbytes, u8 crc) +{ + /* loop over the buffer data */ + while (nbytes-- > 0) + crc = table[(crc ^ *pdata++) & 0xff]; + + return crc; +} +EXPORT_SYMBOL(crc8); + +MODULE_DESCRIPTION("CRC8 (by Williams, Ross N.) function"); +MODULE_AUTHOR("Broadcom Corporation"); +MODULE_LICENSE("Dual BSD/GPL"); diff --git a/lib/kstrtox.h b/lib/kstrtox.h new file mode 100644 index 0000000..f13eeea --- /dev/null +++ b/lib/kstrtox.h @@ -0,0 +1,8 @@ +#ifndef _LIB_KSTRTOX_H +#define _LIB_KSTRTOX_H + +#define KSTRTOX_OVERFLOW (1U << 31) +const char *_parse_integer_fixup_radix(const char *s, unsigned int *base); +unsigned int _parse_integer(const char *s, unsigned int base, unsigned long long *res); + +#endif diff --git a/lib/llist.c b/lib/llist.c new file mode 100644 index 0000000..700cff7 --- /dev/null +++ b/lib/llist.c @@ -0,0 +1,89 @@ +/* + * Lock-less NULL terminated single linked list + * + * The basic atomic operation of this list is cmpxchg on long. On + * architectures that don't have NMI-safe cmpxchg implementation, the + * list can NOT be used in NMI handlers. So code that uses the list in + * an NMI handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG. + * + * Copyright 2010,2011 Intel Corp. + * Author: Huang Ying <ying.huang@intel.com> + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License version + * 2 as published by the Free Software Foundation; + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ +#include <linux/kernel.h> +#include <linux/module.h> +#include <linux/interrupt.h> +#include <linux/llist.h> + +#include <asm/system.h> + +/** + * llist_add_batch - add several linked entries in batch + * @new_first: first entry in batch to be added + * @new_last: last entry in batch to be added + * @head: the head for your lock-less list + * + * Return whether list is empty before adding. + */ +bool llist_add_batch(struct llist_node *new_first, struct llist_node *new_last, + struct llist_head *head) +{ + struct llist_node *entry, *old_entry; + + entry = head->first; + for (;;) { + old_entry = entry; + new_last->next = entry; + entry = cmpxchg(&head->first, old_entry, new_first); + if (entry == old_entry) + break; + } + + return old_entry == NULL; +} +EXPORT_SYMBOL_GPL(llist_add_batch); + +/** + * llist_del_first - delete the first entry of lock-less list + * @head: the head for your lock-less list + * + * If list is empty, return NULL, otherwise, return the first entry + * deleted, this is the newest added one. + * + * Only one llist_del_first user can be used simultaneously with + * multiple llist_add users without lock. Because otherwise + * llist_del_first, llist_add, llist_add (or llist_del_all, llist_add, + * llist_add) sequence in another user may change @head->first->next, + * but keep @head->first. If multiple consumers are needed, please + * use llist_del_all or use lock between consumers. + */ +struct llist_node *llist_del_first(struct llist_head *head) +{ + struct llist_node *entry, *old_entry, *next; + + entry = head->first; + for (;;) { + if (entry == NULL) + return NULL; + old_entry = entry; + next = entry->next; + entry = cmpxchg(&head->first, old_entry, next); + if (entry == old_entry) + break; + } + + return entry; +} +EXPORT_SYMBOL_GPL(llist_del_first); diff --git a/lib/lzo/lzo1x_decompress_safe.c b/lib/lzo/lzo1x_decompress_safe.c new file mode 100644 index 0000000..a1c387f --- /dev/null +++ b/lib/lzo/lzo1x_decompress_safe.c @@ -0,0 +1,268 @@ +/* + * LZO1X Decompressor from LZO + * + * Copyright (C) 1996-2012 Markus F.X.J. Oberhumer <markus@oberhumer.com> + * + * The full LZO package can be found at: + * http://www.oberhumer.com/opensource/lzo/ + * + * Changed for Linux kernel use by: + * Nitin Gupta <nitingupta910@gmail.com> + * Richard Purdie <rpurdie@openedhand.com> + */ + +#ifndef STATIC +#include <linux/module.h> +#include <linux/kernel.h> +#endif +#include <asm/unaligned.h> +#include <linux/lzo.h> +#include "lzodefs.h" + +#define HAVE_IP(x) ((size_t)(ip_end - ip) >= (size_t)(x)) +#define HAVE_OP(x) ((size_t)(op_end - op) >= (size_t)(x)) +#define NEED_IP(x) if (!HAVE_IP(x)) goto input_overrun +#define NEED_OP(x) if (!HAVE_OP(x)) goto output_overrun +#define TEST_LB(m_pos) if ((m_pos) < out) goto lookbehind_overrun + +/* This MAX_255_COUNT is the maximum number of times we can add 255 to a base + * count without overflowing an integer. The multiply will overflow when + * multiplying 255 by more than MAXINT/255. The sum will overflow earlier + * depending on the base count. Since the base count is taken from a u8 + * and a few bits, it is safe to assume that it will always be lower than + * or equal to 2*255, thus we can always prevent any overflow by accepting + * two less 255 steps. See Documentation/lzo.txt for more information. + */ +#define MAX_255_COUNT ((((size_t)~0) / 255) - 2) + +int lzo1x_decompress_safe(const unsigned char *in, size_t in_len, + unsigned char *out, size_t *out_len) +{ + unsigned char *op; + const unsigned char *ip; + size_t t, next; + size_t state = 0; + const unsigned char *m_pos; + const unsigned char * const ip_end = in + in_len; + unsigned char * const op_end = out + *out_len; + + op = out; + ip = in; + + if (unlikely(in_len < 3)) + goto input_overrun; + if (*ip > 17) { + t = *ip++ - 17; + if (t < 4) { + next = t; + goto match_next; + } + goto copy_literal_run; + } + + for (;;) { + t = *ip++; + if (t < 16) { + if (likely(state == 0)) { + if (unlikely(t == 0)) { + size_t offset; + const unsigned char *ip_last = ip; + + while (unlikely(*ip == 0)) { + ip++; + NEED_IP(1); + } + offset = ip - ip_last; + if (unlikely(offset > MAX_255_COUNT)) + return LZO_E_ERROR; + + offset = (offset << 8) - offset; + t += offset + 15 + *ip++; + } + t += 3; +copy_literal_run: +#if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) + if (likely(HAVE_IP(t + 15) && HAVE_OP(t + 15))) { + const unsigned char *ie = ip + t; + unsigned char *oe = op + t; + do { + COPY8(op, ip); + op += 8; + ip += 8; + COPY8(op, ip); + op += 8; + ip += 8; + } while (ip < ie); + ip = ie; + op = oe; + } else +#endif + { + NEED_OP(t); + NEED_IP(t + 3); + do { + *op++ = *ip++; + } while (--t > 0); + } + state = 4; + continue; + } else if (state != 4) { + next = t & 3; + m_pos = op - 1; + m_pos -= t >> 2; + m_pos -= *ip++ << 2; + TEST_LB(m_pos); + NEED_OP(2); + op[0] = m_pos[0]; + op[1] = m_pos[1]; + op += 2; + goto match_next; + } else { + next = t & 3; + m_pos = op - (1 + M2_MAX_OFFSET); + m_pos -= t >> 2; + m_pos -= *ip++ << 2; + t = 3; + } + } else if (t >= 64) { + next = t & 3; + m_pos = op - 1; + m_pos -= (t >> 2) & 7; + m_pos -= *ip++ << 3; + t = (t >> 5) - 1 + (3 - 1); + } else if (t >= 32) { + t = (t & 31) + (3 - 1); + if (unlikely(t == 2)) { + size_t offset; + const unsigned char *ip_last = ip; + + while (unlikely(*ip == 0)) { + ip++; + NEED_IP(1); + } + offset = ip - ip_last; + if (unlikely(offset > MAX_255_COUNT)) + return LZO_E_ERROR; + + offset = (offset << 8) - offset; + t += offset + 31 + *ip++; + NEED_IP(2); + } + m_pos = op - 1; + next = get_unaligned_le16(ip); + ip += 2; + m_pos -= next >> 2; + next &= 3; + } else { + m_pos = op; + m_pos -= (t & 8) << 11; + t = (t & 7) + (3 - 1); + if (unlikely(t == 2)) { + size_t offset; + const unsigned char *ip_last = ip; + + while (unlikely(*ip == 0)) { + ip++; + NEED_IP(1); + } + offset = ip - ip_last; + if (unlikely(offset > MAX_255_COUNT)) + return LZO_E_ERROR; + + offset = (offset << 8) - offset; + t += offset + 7 + *ip++; + NEED_IP(2); + } + next = get_unaligned_le16(ip); + ip += 2; + m_pos -= next >> 2; + next &= 3; + if (m_pos == op) + goto eof_found; + m_pos -= 0x4000; + } + TEST_LB(m_pos); +#if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) + if (op - m_pos >= 8) { + unsigned char *oe = op + t; + if (likely(HAVE_OP(t + 15))) { + do { + COPY8(op, m_pos); + op += 8; + m_pos += 8; + COPY8(op, m_pos); + op += 8; + m_pos += 8; + } while (op < oe); + op = oe; + if (HAVE_IP(6)) { + state = next; + COPY4(op, ip); + op += next; + ip += next; + continue; + } + } else { + NEED_OP(t); + do { + *op++ = *m_pos++; + } while (op < oe); + } + } else +#endif + { + unsigned char *oe = op + t; + NEED_OP(t); + op[0] = m_pos[0]; + op[1] = m_pos[1]; + op += 2; + m_pos += 2; + do { + *op++ = *m_pos++; + } while (op < oe); + } +match_next: + state = next; + t = next; +#if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) + if (likely(HAVE_IP(6) && HAVE_OP(4))) { + COPY4(op, ip); + op += t; + ip += t; + } else +#endif + { + NEED_IP(t + 3); + NEED_OP(t); + while (t > 0) { + *op++ = *ip++; + t--; + } + } + } + +eof_found: + *out_len = op - out; + return (t != 3 ? LZO_E_ERROR : + ip == ip_end ? LZO_E_OK : + ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN); + +input_overrun: + *out_len = op - out; + return LZO_E_INPUT_OVERRUN; + +output_overrun: + *out_len = op - out; + return LZO_E_OUTPUT_OVERRUN; + +lookbehind_overrun: + *out_len = op - out; + return LZO_E_LOOKBEHIND_OVERRUN; +} +#ifndef STATIC +EXPORT_SYMBOL_GPL(lzo1x_decompress_safe); + +MODULE_LICENSE("GPL"); +MODULE_DESCRIPTION("LZO1X Decompressor"); + +#endif |