diff options
| author | Srinivasarao P <spathi@codeaurora.org> | 2018-08-28 17:27:24 +0530 |
|---|---|---|
| committer | Srinivasarao P <spathi@codeaurora.org> | 2018-08-28 17:28:39 +0530 |
| commit | b87d31674ac9e8203f3a30b53f6a697bf5cf36b6 (patch) | |
| tree | 6b9b8869b7d60d93b4c78b5ab2cd03b3f4a5a2e6 /lib/zstd/fse_decompress.c | |
| parent | 40eed1f50062df731c0bf79af27c463b7d2003a1 (diff) | |
| parent | 5e24b4e4d3724968a1c106e9dae091ef4dfc578e (diff) | |
Merge android-4.4.153 (5e24b4e) into msm-4.4
* refs/heads/tmp-5e24b4e
Linux 4.4.153
ovl: warn instead of error if d_type is not supported
ovl: Do d_type check only if work dir creation was successful
ovl: Ensure upper filesystem supports d_type
x86/mm: Fix use-after-free of ldt_struct
x86/mm/pat: Fix L1TF stable backport for CPA
ANDROID: x86_64_cuttlefish_defconfig: Enable lz4 compression for zram
UPSTREAM: drivers/block/zram/zram_drv.c: fix bug storing backing_dev
BACKPORT: zram: introduce zram memory tracking
BACKPORT: zram: record accessed second
BACKPORT: zram: mark incompressible page as ZRAM_HUGE
UPSTREAM: zram: correct flag name of ZRAM_ACCESS
UPSTREAM: zram: Delete gendisk before cleaning up the request queue
UPSTREAM: drivers/block/zram/zram_drv.c: make zram_page_end_io() static
BACKPORT: zram: set BDI_CAP_STABLE_WRITES once
UPSTREAM: zram: fix null dereference of handle
UPSTREAM: zram: add config and doc file for writeback feature
BACKPORT: zram: read page from backing device
BACKPORT: zram: write incompressible pages to backing device
BACKPORT: zram: identify asynchronous IO's return value
BACKPORT: zram: add free space management in backing device
UPSTREAM: zram: add interface to specif backing device
UPSTREAM: zram: rename zram_decompress_page to __zram_bvec_read
UPSTREAM: zram: inline zram_compress
UPSTREAM: zram: clean up duplicated codes in __zram_bvec_write
Linux 4.4.152
reiserfs: fix broken xattr handling (heap corruption, bad retval)
i2c: imx: Fix race condition in dma read
PCI: pciehp: Fix use-after-free on unplug
PCI: Skip MPS logic for Virtual Functions (VFs)
PCI: hotplug: Don't leak pci_slot on registration failure
parisc: Remove unnecessary barriers from spinlock.h
bridge: Propagate vlan add failure to user
packet: refine ring v3 block size test to hold one frame
netfilter: conntrack: dccp: treat SYNC/SYNCACK as invalid if no prior state
xfrm_user: prevent leaking 2 bytes of kernel memory
parisc: Remove ordered stores from syscall.S
ext4: fix spectre gadget in ext4_mb_regular_allocator()
KVM: irqfd: fix race between EPOLLHUP and irq_bypass_register_consumer
staging: android: ion: check for kref overflow
tcp: identify cryptic messages as TCP seq # bugs
net: qca_spi: Fix log level if probe fails
net: qca_spi: Make sure the QCA7000 reset is triggered
net: qca_spi: Avoid packet drop during initial sync
net: usb: rtl8150: demote allmulti message to dev_dbg()
net/ethernet/freescale/fman: fix cross-build error
drm/nouveau/gem: off by one bugs in nouveau_gem_pushbuf_reloc_apply()
tcp: remove DELAYED ACK events in DCTCP
qlogic: check kstrtoul() for errors
packet: reset network header if packet shorter than ll reserved space
ixgbe: Be more careful when modifying MAC filters
ARM: dts: am3517.dtsi: Disable reference to OMAP3 OTG controller
ARM: 8780/1: ftrace: Only set kernel memory back to read-only after boot
perf llvm-utils: Remove bashism from kernel include fetch script
bnxt_en: Fix for system hang if request_irq fails
drm/armada: fix colorkey mode property
ieee802154: fakelb: switch from BUG_ON() to WARN_ON() on problem
ieee802154: at86rf230: use __func__ macro for debug messages
ieee802154: at86rf230: switch from BUG_ON() to WARN_ON() on problem
ARM: pxa: irq: fix handling of ICMR registers in suspend/resume
netfilter: x_tables: set module owner for icmp(6) matches
smsc75xx: Add workaround for gigabit link up hardware errata.
kasan: fix shadow_size calculation error in kasan_module_alloc
tracing: Use __printf markup to silence compiler
ARM: imx_v4_v5_defconfig: Select ULPI support
ARM: imx_v6_v7_defconfig: Select ULPI support
HID: wacom: Correct touch maximum XY of 2nd-gen Intuos
m68k: fix "bad page state" oops on ColdFire boot
bnx2x: Fix receiving tx-timeout in error or recovery state.
drm/exynos: decon5433: Fix WINCONx reset value
drm/exynos: decon5433: Fix per-plane global alpha for XRGB modes
drm/exynos: gsc: Fix support for NV16/61, YUV420/YVU420 and YUV422 modes
md/raid10: fix that replacement cannot complete recovery after reassemble
dmaengine: k3dma: Off by one in k3_of_dma_simple_xlate()
ARM: dts: da850: Fix interrups property for gpio
selftests/x86/sigreturn/64: Fix spurious failures on AMD CPUs
perf report powerpc: Fix crash if callchain is empty
perf test session topology: Fix test on s390
usb: xhci: increase CRS timeout value
ARM: dts: am437x: make edt-ft5x06 a wakeup source
brcmfmac: stop watchdog before detach and free everything
cxgb4: when disabling dcb set txq dcb priority to 0
Smack: Mark inode instant in smack_task_to_inode
ipv6: mcast: fix unsolicited report interval after receiving querys
locking/lockdep: Do not record IRQ state within lockdep code
net: davinci_emac: match the mdio device against its compatible if possible
ARC: Enable machine_desc->init_per_cpu for !CONFIG_SMP
net: propagate dev_get_valid_name return code
net: hamradio: use eth_broadcast_addr
enic: initialize enic->rfs_h.lock in enic_probe
qed: Add sanity check for SIMD fastpath handler.
arm64: make secondary_start_kernel() notrace
scsi: xen-scsifront: add error handling for xenbus_printf
usb: gadget: dwc2: fix memory leak in gadget_init()
usb: gadget: composite: fix delayed_status race condition when set_interface
usb: dwc2: fix isoc split in transfer with no data
ARM: dts: Cygnus: Fix I2C controller interrupt type
selftests: sync: add config fragment for testing sync framework
selftests: zram: return Kselftest Skip code for skipped tests
selftests: user: return Kselftest Skip code for skipped tests
selftests: static_keys: return Kselftest Skip code for skipped tests
selftests: pstore: return Kselftest Skip code for skipped tests
netfilter: ipv6: nf_defrag: reduce struct net memory waste
ARC: Explicitly add -mmedium-calls to CFLAGS
ANDROID: x86_64_cuttlefish_defconfig: Enable zram and zstd
BACKPORT: crypto: zstd - Add zstd support
UPSTREAM: zram: add zstd to the supported algorithms list
UPSTREAM: lib: Add zstd modules
UPSTREAM: lib: Add xxhash module
UPSTREAM: zram: rework copy of compressor name in comp_algorithm_store()
UPSTREAM: zram: constify attribute_group structures.
UPSTREAM: zram: count same page write as page_stored
UPSTREAM: zram: reduce load operation in page_same_filled
UPSTREAM: zram: use zram_free_page instead of open-coded
UPSTREAM: zram: introduce zram data accessor
UPSTREAM: zram: remove zram_meta structure
UPSTREAM: zram: use zram_slot_lock instead of raw bit_spin_lock op
BACKPORT: zram: partial IO refactoring
BACKPORT: zram: handle multiple pages attached bio's bvec
UPSTREAM: zram: fix operator precedence to get offset
BACKPORT: zram: extend zero pages to same element pages
BACKPORT: zram: remove waitqueue for IO done
UPSTREAM: zram: remove obsolete sysfs attrs
UPSTREAM: zram: support BDI_CAP_STABLE_WRITES
UPSTREAM: zram: revalidate disk under init_lock
BACKPORT: mm: support anonymous stable page
UPSTREAM: zram: use __GFP_MOVABLE for memory allocation
UPSTREAM: zram: drop gfp_t from zcomp_strm_alloc()
UPSTREAM: zram: add more compression algorithms
UPSTREAM: zram: delete custom lzo/lz4
UPSTREAM: zram: cosmetic: cleanup documentation
UPSTREAM: zram: use crypto api to check alg availability
BACKPORT: zram: switch to crypto compress API
UPSTREAM: zram: rename zstrm find-release functions
UPSTREAM: zram: introduce per-device debug_stat sysfs node
UPSTREAM: zram: remove max_comp_streams internals
UPSTREAM: zram: user per-cpu compression streams
BACKPORT: zsmalloc: require GFP in zs_malloc()
UPSTREAM: zram/zcomp: do not zero out zcomp private pages
UPSTREAM: zram: pass gfp from zcomp frontend to backend
UPSTREAM: socket: close race condition between sock_close() and sockfs_setattr()
ANDROID: Refresh x86_64_cuttlefish_defconfig
Linux 4.4.151
isdn: Disable IIOCDBGVAR
Bluetooth: avoid killing an already killed socket
x86/mm: Simplify p[g4um]d_page() macros
serial: 8250_dw: always set baud rate in dw8250_set_termios
ACPI / PM: save NVS memory for ASUS 1025C laptop
ACPI: save NVS memory for Lenovo G50-45
USB: option: add support for DW5821e
USB: serial: sierra: fix potential deadlock at close
ALSA: vxpocket: Fix invalid endian conversions
ALSA: memalloc: Don't exceed over the requested size
ALSA: hda: Correct Asrock B85M-ITX power_save blacklist entry
ALSA: cs5535audio: Fix invalid endian conversion
ALSA: virmidi: Fix too long output trigger loop
ALSA: vx222: Fix invalid endian conversions
ALSA: hda - Turn CX8200 into D3 as well upon reboot
ALSA: hda - Sleep for 10ms after entering D3 on Conexant codecs
net_sched: fix NULL pointer dereference when delete tcindex filter
vsock: split dwork to avoid reinitializations
net_sched: Fix missing res info when create new tc_index filter
llc: use refcount_inc_not_zero() for llc_sap_find()
l2tp: use sk_dst_check() to avoid race on sk->sk_dst_cache
dccp: fix undefined behavior with 'cwnd' shift in ccid2_cwnd_restart()
Conflicts:
drivers/block/zram/zram_drv.c
drivers/staging/android/ion/ion.c
include/linux/swap.h
mm/zsmalloc.c
Change-Id: I1c437ac5133503a939d06d51ec778b65371df6d1
Signed-off-by: Srinivasarao P <spathi@codeaurora.org>
Diffstat (limited to 'lib/zstd/fse_decompress.c')
| -rw-r--r-- | lib/zstd/fse_decompress.c | 332 |
1 files changed, 332 insertions, 0 deletions
diff --git a/lib/zstd/fse_decompress.c b/lib/zstd/fse_decompress.c new file mode 100644 index 000000000000..a84300e5a013 --- /dev/null +++ b/lib/zstd/fse_decompress.c @@ -0,0 +1,332 @@ +/* + * FSE : Finite State Entropy decoder + * Copyright (C) 2013-2015, Yann Collet. + * + * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * 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 dual-licensed; you may select + * either version 2 of the GNU General Public License ("GPL") or BSD license + * ("BSD"). + * + * You can contact the author at : + * - Source repository : https://github.com/Cyan4973/FiniteStateEntropy + */ + +/* ************************************************************** +* Compiler specifics +****************************************************************/ +#define FORCE_INLINE static __always_inline + +/* ************************************************************** +* Includes +****************************************************************/ +#include "bitstream.h" +#include "fse.h" +#include <linux/compiler.h> +#include <linux/kernel.h> +#include <linux/string.h> /* memcpy, memset */ + +/* ************************************************************** +* Error Management +****************************************************************/ +#define FSE_isError ERR_isError +#define FSE_STATIC_ASSERT(c) \ + { \ + enum { FSE_static_assert = 1 / (int)(!!(c)) }; \ + } /* use only *after* variable declarations */ + +/* check and forward error code */ +#define CHECK_F(f) \ + { \ + size_t const e = f; \ + if (FSE_isError(e)) \ + return e; \ + } + +/* ************************************************************** +* Templates +****************************************************************/ +/* + designed to be included + for type-specific functions (template emulation in C) + Objective is to write these functions only once, for improved maintenance +*/ + +/* safety checks */ +#ifndef FSE_FUNCTION_EXTENSION +#error "FSE_FUNCTION_EXTENSION must be defined" +#endif +#ifndef FSE_FUNCTION_TYPE +#error "FSE_FUNCTION_TYPE must be defined" +#endif + +/* Function names */ +#define FSE_CAT(X, Y) X##Y +#define FSE_FUNCTION_NAME(X, Y) FSE_CAT(X, Y) +#define FSE_TYPE_NAME(X, Y) FSE_CAT(X, Y) + +/* Function templates */ + +size_t FSE_buildDTable_wksp(FSE_DTable *dt, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void *workspace, size_t workspaceSize) +{ + void *const tdPtr = dt + 1; /* because *dt is unsigned, 32-bits aligned on 32-bits */ + FSE_DECODE_TYPE *const tableDecode = (FSE_DECODE_TYPE *)(tdPtr); + U16 *symbolNext = (U16 *)workspace; + + U32 const maxSV1 = maxSymbolValue + 1; + U32 const tableSize = 1 << tableLog; + U32 highThreshold = tableSize - 1; + + /* Sanity Checks */ + if (workspaceSize < sizeof(U16) * (FSE_MAX_SYMBOL_VALUE + 1)) + return ERROR(tableLog_tooLarge); + if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) + return ERROR(maxSymbolValue_tooLarge); + if (tableLog > FSE_MAX_TABLELOG) + return ERROR(tableLog_tooLarge); + + /* Init, lay down lowprob symbols */ + { + FSE_DTableHeader DTableH; + DTableH.tableLog = (U16)tableLog; + DTableH.fastMode = 1; + { + S16 const largeLimit = (S16)(1 << (tableLog - 1)); + U32 s; + for (s = 0; s < maxSV1; s++) { + if (normalizedCounter[s] == -1) { + tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s; + symbolNext[s] = 1; + } else { + if (normalizedCounter[s] >= largeLimit) + DTableH.fastMode = 0; + symbolNext[s] = normalizedCounter[s]; + } + } + } + memcpy(dt, &DTableH, sizeof(DTableH)); + } + + /* Spread symbols */ + { + U32 const tableMask = tableSize - 1; + U32 const step = FSE_TABLESTEP(tableSize); + U32 s, position = 0; + for (s = 0; s < maxSV1; s++) { + int i; + for (i = 0; i < normalizedCounter[s]; i++) { + tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s; + position = (position + step) & tableMask; + while (position > highThreshold) + position = (position + step) & tableMask; /* lowprob area */ + } + } + if (position != 0) + return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */ + } + + /* Build Decoding table */ + { + U32 u; + for (u = 0; u < tableSize; u++) { + FSE_FUNCTION_TYPE const symbol = (FSE_FUNCTION_TYPE)(tableDecode[u].symbol); + U16 nextState = symbolNext[symbol]++; + tableDecode[u].nbBits = (BYTE)(tableLog - BIT_highbit32((U32)nextState)); + tableDecode[u].newState = (U16)((nextState << tableDecode[u].nbBits) - tableSize); + } + } + + return 0; +} + +/*-******************************************************* +* Decompression (Byte symbols) +*********************************************************/ +size_t FSE_buildDTable_rle(FSE_DTable *dt, BYTE symbolValue) +{ + void *ptr = dt; + FSE_DTableHeader *const DTableH = (FSE_DTableHeader *)ptr; + void *dPtr = dt + 1; + FSE_decode_t *const cell = (FSE_decode_t *)dPtr; + + DTableH->tableLog = 0; + DTableH->fastMode = 0; + + cell->newState = 0; + cell->symbol = symbolValue; + cell->nbBits = 0; + + return 0; +} + +size_t FSE_buildDTable_raw(FSE_DTable *dt, unsigned nbBits) +{ + void *ptr = dt; + FSE_DTableHeader *const DTableH = (FSE_DTableHeader *)ptr; + void *dPtr = dt + 1; + FSE_decode_t *const dinfo = (FSE_decode_t *)dPtr; + const unsigned tableSize = 1 << nbBits; + const unsigned tableMask = tableSize - 1; + const unsigned maxSV1 = tableMask + 1; + unsigned s; + + /* Sanity checks */ + if (nbBits < 1) + return ERROR(GENERIC); /* min size */ + + /* Build Decoding Table */ + DTableH->tableLog = (U16)nbBits; + DTableH->fastMode = 1; + for (s = 0; s < maxSV1; s++) { + dinfo[s].newState = 0; + dinfo[s].symbol = (BYTE)s; + dinfo[s].nbBits = (BYTE)nbBits; + } + + return 0; +} + +FORCE_INLINE size_t FSE_decompress_usingDTable_generic(void *dst, size_t maxDstSize, const void *cSrc, size_t cSrcSize, const FSE_DTable *dt, + const unsigned fast) +{ + BYTE *const ostart = (BYTE *)dst; + BYTE *op = ostart; + BYTE *const omax = op + maxDstSize; + BYTE *const olimit = omax - 3; + + BIT_DStream_t bitD; + FSE_DState_t state1; + FSE_DState_t state2; + + /* Init */ + CHECK_F(BIT_initDStream(&bitD, cSrc, cSrcSize)); + + FSE_initDState(&state1, &bitD, dt); + FSE_initDState(&state2, &bitD, dt); + +#define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD) + + /* 4 symbols per loop */ + for (; (BIT_reloadDStream(&bitD) == BIT_DStream_unfinished) & (op < olimit); op += 4) { + op[0] = FSE_GETSYMBOL(&state1); + + if (FSE_MAX_TABLELOG * 2 + 7 > sizeof(bitD.bitContainer) * 8) /* This test must be static */ + BIT_reloadDStream(&bitD); + + op[1] = FSE_GETSYMBOL(&state2); + + if (FSE_MAX_TABLELOG * 4 + 7 > sizeof(bitD.bitContainer) * 8) /* This test must be static */ + { + if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) { + op += 2; + break; + } + } + + op[2] = FSE_GETSYMBOL(&state1); + + if (FSE_MAX_TABLELOG * 2 + 7 > sizeof(bitD.bitContainer) * 8) /* This test must be static */ + BIT_reloadDStream(&bitD); + + op[3] = FSE_GETSYMBOL(&state2); + } + + /* tail */ + /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */ + while (1) { + if (op > (omax - 2)) + return ERROR(dstSize_tooSmall); + *op++ = FSE_GETSYMBOL(&state1); + if (BIT_reloadDStream(&bitD) == BIT_DStream_overflow) { + *op++ = FSE_GETSYMBOL(&state2); + break; + } + + if (op > (omax - 2)) + return ERROR(dstSize_tooSmall); + *op++ = FSE_GETSYMBOL(&state2); + if (BIT_reloadDStream(&bitD) == BIT_DStream_overflow) { + *op++ = FSE_GETSYMBOL(&state1); + break; + } + } + + return op - ostart; +} + +size_t FSE_decompress_usingDTable(void *dst, size_t originalSize, const void *cSrc, size_t cSrcSize, const FSE_DTable *dt) +{ + const void *ptr = dt; + const FSE_DTableHeader *DTableH = (const FSE_DTableHeader *)ptr; + const U32 fastMode = DTableH->fastMode; + + /* select fast mode (static) */ + if (fastMode) + return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1); + return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0); +} + +size_t FSE_decompress_wksp(void *dst, size_t dstCapacity, const void *cSrc, size_t cSrcSize, unsigned maxLog, void *workspace, size_t workspaceSize) +{ + const BYTE *const istart = (const BYTE *)cSrc; + const BYTE *ip = istart; + unsigned tableLog; + unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE; + size_t NCountLength; + + FSE_DTable *dt; + short *counting; + size_t spaceUsed32 = 0; + + FSE_STATIC_ASSERT(sizeof(FSE_DTable) == sizeof(U32)); + + dt = (FSE_DTable *)((U32 *)workspace + spaceUsed32); + spaceUsed32 += FSE_DTABLE_SIZE_U32(maxLog); + counting = (short *)((U32 *)workspace + spaceUsed32); + spaceUsed32 += ALIGN(sizeof(short) * (FSE_MAX_SYMBOL_VALUE + 1), sizeof(U32)) >> 2; + + if ((spaceUsed32 << 2) > workspaceSize) + return ERROR(tableLog_tooLarge); + workspace = (U32 *)workspace + spaceUsed32; + workspaceSize -= (spaceUsed32 << 2); + + /* normal FSE decoding mode */ + NCountLength = FSE_readNCount(counting, &maxSymbolValue, &tableLog, istart, cSrcSize); + if (FSE_isError(NCountLength)) + return NCountLength; + // if (NCountLength >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size; supposed to be already checked in NCountLength, only remaining + // case : NCountLength==cSrcSize */ + if (tableLog > maxLog) + return ERROR(tableLog_tooLarge); + ip += NCountLength; + cSrcSize -= NCountLength; + + CHECK_F(FSE_buildDTable_wksp(dt, counting, maxSymbolValue, tableLog, workspace, workspaceSize)); + + return FSE_decompress_usingDTable(dst, dstCapacity, ip, cSrcSize, dt); /* always return, even if it is an error code */ +} |
