mirror of
https://github.com/torvalds/linux.git
synced 2026-05-27 08:33:17 +02:00
4460e9c68d
This patch implements several micro-optimizations on lz77_compress() with the goal of reducing the number of instructions per [input] byte (a.k.a. IPB). Changes: - change hashtable to be u32 (instead of u64) -- change the hash function to reflect that (adds lz77_hash() and lz77_read32() helpers) - batch-write literals instead of 1 by 1 -- now that we have a well defined hot path (match finding) and a cold path (encode literals + match), batch writing makes a significant difference - implement adaptive skipping of input bytes -- skip input bytes more aggressively if too few matches are being found - name some constants for more meaningful context Signed-off-by: Enzo Matsumiya <ematsumiya@suse.de> Signed-off-by: Steve French <stfrench@microsoft.com>
44 lines
1.4 KiB
C
44 lines
1.4 KiB
C
/* SPDX-License-Identifier: GPL-2.0-only */
|
|
/*
|
|
* Copyright (C) 2024-2026, SUSE LLC
|
|
*
|
|
* Authors: Enzo Matsumiya <ematsumiya@suse.de>
|
|
*
|
|
* Implementation of the LZ77 "plain" compression algorithm, as per MS-XCA spec.
|
|
*/
|
|
#ifndef _SMB_COMPRESS_LZ77_H
|
|
#define _SMB_COMPRESS_LZ77_H
|
|
|
|
#include <linux/kernel.h>
|
|
|
|
/**
|
|
* lz77_compressed_alloc_size() - Compute compressed buffer size.
|
|
* @size: uncompressed (src) size
|
|
*
|
|
* Compute allocation size for the compressed buffer based on uncompressed size.
|
|
* Accounts for metadata and overprovision for the worst case scenario.
|
|
*
|
|
* LZ77 metadata is a 4-byte flag that is written:
|
|
* - on dst begin (pos 0)
|
|
* - every 32 literals or matches
|
|
* - on end-of-stream (possibly, if last write was another flag)
|
|
*
|
|
* Worst case scenario is an all-literal compression, which means:
|
|
* metadata bytes = 4 + ((@size / 32) * 4) + 4, or, simplified, (@size >> 3) + 8
|
|
*
|
|
* The worst case scenario rarely happens, but such overprovisioning also allows lz77_compress()
|
|
* main loop to run without ever bound checking dst, which is a huge perf improvement, while also
|
|
* being safe when compression goes bad.
|
|
*
|
|
* Return: required (*) allocation size for compressed buffer.
|
|
*
|
|
* (*) checked once in the beginning of lz77_compress()
|
|
*/
|
|
static __always_inline u32 lz77_compressed_alloc_size(const u32 size)
|
|
{
|
|
return size + (size >> 3) + 8;
|
|
}
|
|
|
|
int lz77_compress(const void *src, const u32 slen, void *dst, u32 *dlen);
|
|
#endif /* _SMB_COMPRESS_LZ77_H */
|