From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-9.0 required=3.0 tests=DKIMWL_WL_MED,DKIM_SIGNED, DKIM_VALID,HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI, SIGNED_OFF_BY,SPF_PASS,URIBL_BLOCKED,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id B7ECFC64EB4 for ; Fri, 30 Nov 2018 11:47:57 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 5BECB2082F for ; Fri, 30 Nov 2018 11:47:57 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (1024-bit key) header.d=armh.onmicrosoft.com header.i=@armh.onmicrosoft.com header.b="keQI+QoP" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 5BECB2082F Authentication-Results: mail.kernel.org; dmarc=none (p=none dis=none) header.from=arm.com Authentication-Results: mail.kernel.org; spf=none smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727108AbeK3W44 (ORCPT ); Fri, 30 Nov 2018 17:56:56 -0500 Received: from mail-eopbgr60087.outbound.protection.outlook.com ([40.107.6.87]:40138 "EHLO EUR04-DB3-obe.outbound.protection.outlook.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1726572AbeK3W4z (ORCPT ); Fri, 30 Nov 2018 17:56:55 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector1-arm-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=n6YmpzRlEEmU9GTJdIV+fEo0WnvTJGl/ZMCrki88Bk8=; b=keQI+QoPytD15HW9glV13RIjYKBbHBghIBsqNAJ3J613sGXT/Sc0QNfIcGi3SgjvuujEnKuGyxqBfi5x0qOA3+lxdkpnl1MAc6PbhKH2MGBx7aV5D+irnzTAMys6ypA/OpsUV/MW+8VCUN1QTbQneYDVZQWRWUT3gilyFDLr1ag= Received: from VI1PR0802MB2528.eurprd08.prod.outlook.com (10.175.20.142) by VI1PR0802MB2157.eurprd08.prod.outlook.com (10.172.12.14) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1382.18; Fri, 30 Nov 2018 11:47:45 +0000 Received: from VI1PR0802MB2528.eurprd08.prod.outlook.com ([fe80::3d5c:5229:b634:b1ac]) by VI1PR0802MB2528.eurprd08.prod.outlook.com ([fe80::3d5c:5229:b634:b1ac%11]) with mapi id 15.20.1382.020; Fri, 30 Nov 2018 11:47:45 +0000 From: Dave Rodgman To: "linux-kernel@vger.kernel.org" , "akpm@linux-foundation.org" CC: "herbert@gondor.apana.org.au" , "davem@davemloft.net" , Matt Sealey , "nitingupta910@gmail.com" , "markus@oberhumer.com" , "minchan@kernel.org" , "sergey.senozhatsky.work@gmail.com" , "sonnyrao@google.com" , "gregkh@linuxfoundation.org" , nd Subject: [PATCH 6/8] lib/lzo: implement run-length encoding Thread-Topic: [PATCH 6/8] lib/lzo: implement run-length encoding Thread-Index: AQHUiKKC0yt7OQ1V0keFnLNTm6NvnQ== Date: Fri, 30 Nov 2018 11:47:45 +0000 Message-ID: <20181130114715.27523-7-dave.rodgman@arm.com> References: <20181130114715.27523-1-dave.rodgman@arm.com> In-Reply-To: <20181130114715.27523-1-dave.rodgman@arm.com> Accept-Language: en-GB, en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-mailer: git-send-email 2.17.1 x-originating-ip: [217.140.106.53] x-clientproxiedby: CWXP265CA0058.GBRP265.PROD.OUTLOOK.COM (2603:10a6:400:2c::22) To VI1PR0802MB2528.eurprd08.prod.outlook.com (2603:10a6:800:b0::14) authentication-results: spf=none (sender IP is ) smtp.mailfrom=dave.rodgman@arm.com; x-ms-exchange-messagesentrepresentingtype: 1 x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1;VI1PR0802MB2157;6:J+k1t4vdKHLqkdWfDYg3Hhm3XYQ+049ici46cMYfbs3hZtqFhtyShCeDa2SXRdsD8r4BrbTRYYXMU02X7bN3FsD+mPD7Qu5RUPD83IM3Ki+N3eHZkjKd4zafGzHxnVns+Dw66xffZ3HRRKO9PcKbOa7AxgDwpAMHAkdkyBQ6wZJxsz8U4F/cYfaAJM9wBfBOlZlJadhaTJ8zetOdpjqr1bgHOsHL/idZKsEUhLNN/47SWO2HjuCey8W8mXvwsZV+Et8mmKOwfMgeciNwOEBM6BG06WhP1Ic9Q1c3md3o2nN9JI1hQQlqGALSAjByczIGeWcjqrPqeSptdnUj2HFSsJvvH57nkN2Iyr/IO0oIOErBsdSy4DjgCRyegiCG/ipRp8d542T0lrfxXhP+8fi7BatG/xShNvm4dMWbTVKylTkacC0gEIGSNGIHaFuyUstPLeE/9rghpFY4f+KfaxSnrw==;5:iN8fQ2vxtK4TRHJ4OLNniRtTMRzW1c37nxl5a+HPIObn777lYDEKx35GqoMuWT/ZCheHkjaHhek2uBPhJa0cwNsorsO7fk/kJGfDKwqyeQ/XMdYcTgZMuro7AtopEc5YOxQN3DM5PW8Ycyg2B7CoY4LAb2ns79c9yZ2kPfUlBCU=;7:mlefusLDY7Q1ZoGCenwAw4sT5v6lys8haFl0XirIUE670k+cGfFzz3fLqTKQiBCmXrybBBevagURSQ9LkswK7Cs3DD3jPoWW6TQXQSD/zlVizfqLmMQlHgQ8KKr0wzLPgCBLbk+NibjvkcaY1QGywg== x-ms-office365-filtering-correlation-id: ed14ca71-7bfc-476e-f51a-08d656b9a4ea x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: BCL:0;PCL:0;RULEID:(2390098)(7020095)(4652040)(8989299)(4534185)(4627221)(201703031133081)(201702281549075)(8990200)(5600074)(711020)(4618075)(2017052603328)(7153060)(7193020);SRVR:VI1PR0802MB2157; x-ms-traffictypediagnostic: VI1PR0802MB2157: nodisclaimer: True x-microsoft-antispam-prvs: x-ms-exchange-senderadcheck: 1 x-exchange-antispam-report-cfa-test: BCL:0;PCL:0;RULEID:(8211001083)(6040522)(2401047)(8121501046)(5005006)(3231453)(999002)(944501466)(4982022)(52105112)(10201501046)(93006095)(93001095)(3002001)(6055026)(148016)(149066)(150057)(6041310)(20161123558120)(20161123562045)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123564045)(20161123560045)(201708071742011)(7699051)(76991095);SRVR:VI1PR0802MB2157;BCL:0;PCL:0;RULEID:;SRVR:VI1PR0802MB2157; x-forefront-prvs: 087223B4DA x-forefront-antispam-report: SFV:NSPM;SFS:(10009020)(39860400002)(366004)(396003)(346002)(136003)(376002)(199004)(189003)(50226002)(53936002)(26005)(6306002)(4326008)(4744004)(186003)(305945005)(7736002)(97736004)(11346002)(54906003)(316002)(68736007)(6512007)(6436002)(14444005)(6486002)(386003)(6506007)(102836004)(81166006)(81156014)(256004)(76176011)(52116002)(8676002)(476003)(2616005)(71190400001)(446003)(71200400001)(486006)(575784001)(39060400002)(99286004)(86362001)(14454004)(44832011)(106356001)(966005)(478600001)(2906002)(25786009)(105586002)(66066001)(8936002)(7416002)(1076002)(110136005)(2501003)(5660300001)(36756003)(3846002)(6116002);DIR:OUT;SFP:1101;SCL:1;SRVR:VI1PR0802MB2157;H:VI1PR0802MB2528.eurprd08.prod.outlook.com;FPR:;SPF:None;LANG:en;PTR:InfoNoRecords;A:1;MX:1; received-spf: None (protection.outlook.com: arm.com does not designate permitted sender hosts) x-microsoft-antispam-message-info: 69ccaEHfPAnIwSYhsBUGnLqn5W5GBmnfE9TtrOrbBdsEN8O0iJtdr3n7D3gfBBKBCnZiiqzM2KR/lKTVltGrBEaLak09Onlq75leOxE1NQrrVcvzkmYbjilHoYcq2GrKMyyAjCjjGKhivOp/WDGT/Eh5jqwg/XpiGRz+AUofPbCJy6Tlmxm2GLOyOyGaz3c/bR8CsPK7wykURXr/DWCx8NLDI/0Rpmm96II9Y7xV6L7sYoVZWbyckswjo8UqUSbGIW+tbZzEGoyc9/GkvJoHvXlwmUaxBpwiDrLlHzoTQ1Hf89GxhSDSNlGbb5euGVw+qL3oCr1pY1mwzwvBH9VSyGx0amzLgXQocA8BbLLL9Jo= spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-Network-Message-Id: ed14ca71-7bfc-476e-f51a-08d656b9a4ea X-MS-Exchange-CrossTenant-originalarrivaltime: 30 Nov 2018 11:47:45.8076 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR0802MB2157 Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org When using zram, we frequently encounter long runs of zero bytes. This adds a special case which identifies runs of zeros and encodes them using run-length encoding. This is faster for both compression and decompresion. For high-entropy data which doesn't hit this case, impact is minimal. Compression ratio is within a few percent in all cases. This modifies the bitstream in a way which is backwards compatible (i.e., we can decompress old bitstreams, but old versions of lzo cannot decompress new bitstreams). Link: http://lkml.kernel.org/r/20181127161913.23863-7-dave.rodgman@arm.com Signed-off-by: Dave Rodgman Cc: David S. Miller Cc: Greg Kroah-Hartman Cc: Herbert Xu Cc: Markus F.X.J. Oberhumer Cc: Matt Sealey Cc: Minchan Kim Cc: Nitin Gupta Cc: Richard Purdie Cc: Sergey Senozhatsky Cc: Sonny Rao Signed-off-by: Andrew Morton Signed-off-by: Stephen Rothwell --- Documentation/lzo.txt | 35 +++++++++--- include/linux/lzo.h | 2 +- lib/lzo/lzo1x_compress.c | 98 +++++++++++++++++++++++++++++---- lib/lzo/lzo1x_decompress_safe.c | 75 +++++++++++++++++-------- lib/lzo/lzodefs.h | 12 +++- 5 files changed, 180 insertions(+), 42 deletions(-) diff --git a/Documentation/lzo.txt b/Documentation/lzo.txt index 6fa6a93d0949..306c60344ca7 100644 --- a/Documentation/lzo.txt +++ b/Documentation/lzo.txt @@ -78,16 +78,30 @@ Description is an implementation design choice independent on the algorithm or encoding. =20 +Versions + +0: Original version +1: LZO-RLE + +Version 1 of LZO implements an extension to encode runs of zeros using run +length encoding. This improves speed for data with many zeros, which is a +common case for zram. This modifies the bitstream in a backwards compatibl= e way +(v1 can correctly decompress v0 compressed data, but v0 cannot read v1 dat= a). + Byte sequences =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =20 First byte encoding:: =20 - 0..17 : follow regular instruction encoding, see below. It is wort= h - noting that codes 16 and 17 will represent a block copy fr= om - the dictionary which is empty, and that they will always b= e + 0..16 : follow regular instruction encoding, see below. It is wort= h + noting that code 16 will represent a block copy from the + dictionary which is empty, and that it will always be invalid at this place. =20 + 17 : bitstream version. If the first byte is 17, the next byte + gives the bitstream version. If the first byte is not 17, + the bitstream version is 0. + 18..21 : copy 0..3 literals state =3D (byte - 17) =3D 0..3 [ copy literals ] skip byte @@ -140,6 +154,11 @@ Byte sequences state =3D S (copy S literals after this block) End of stream is reached if distance =3D=3D 16384 =20 + In version 1, this instruction is also used to encode a run of zer= os if + distance =3D 0xbfff, i.e. H =3D 1 and the D bits are all 1. + In this case, it is followed by a fourth byte, X. + run length =3D ((X << 3) | (0 0 0 0 0 L L L)) + 4. + 0 0 1 L L L L L (32..63) Copy of small block within 16kB distance (preferably less than = 34B) length =3D 2 + (L ?: 31 + (zero_bytes * 255) + non_zero_byte) @@ -165,7 +184,9 @@ Authors =3D=3D=3D=3D=3D=3D=3D =20 This document was written by Willy Tarreau on 2014/07/19 duri= ng an - analysis of the decompression code available in Linux 3.16-rc5. The code= is - tricky, it is possible that this document contains mistakes or that a fe= w - corner cases were overlooked. In any case, please report any doubt, fix,= or - proposed updates to the author(s) so that the document can be updated. + analysis of the decompression code available in Linux 3.16-rc5, and upda= ted + by Dave Rodgman on 2018/10/30 to introduce run-le= ngth + encoding. The code is tricky, it is possible that this document contains + mistakes or that a few corner cases were overlooked. In any case, please + report any doubt, fix, or proposed updates to the author(s) so that the + document can be updated. diff --git a/include/linux/lzo.h b/include/linux/lzo.h index 2ae27cb89927..547a86c71e1b 100644 --- a/include/linux/lzo.h +++ b/include/linux/lzo.h @@ -18,7 +18,7 @@ #define LZO1X_1_MEM_COMPRESS (8192 * sizeof(unsigned short)) #define LZO1X_MEM_COMPRESS LZO1X_1_MEM_COMPRESS =20 -#define lzo1x_worst_compress(x) ((x) + ((x) / 16) + 64 + 3) +#define lzo1x_worst_compress(x) ((x) + ((x) / 16) + 64 + 3 + 2) =20 /* This requires 'wrkmem' of size LZO1X_1_MEM_COMPRESS */ int lzo1x_1_compress(const unsigned char *src, size_t src_len, diff --git a/lib/lzo/lzo1x_compress.c b/lib/lzo/lzo1x_compress.c index 82fb5571ce5e..fa8d4ff38531 100644 --- a/lib/lzo/lzo1x_compress.c +++ b/lib/lzo/lzo1x_compress.c @@ -20,7 +20,7 @@ static noinline size_t lzo1x_1_do_compress(const unsigned char *in, size_t in_len, unsigned char *out, size_t *out_len, - size_t ti, void *wrkmem) + size_t ti, void *wrkmem, signed char *state_offset) { const unsigned char *ip; unsigned char *op; @@ -38,24 +38,82 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_= len, const unsigned char *m_pos; size_t t, m_len, m_off; u32 dv; + u32 run_length =3D 0; literal: ip +=3D 1 + ((ip - ii) >> 5); next: if (unlikely(ip >=3D ip_end)) break; dv =3D get_unaligned_le32(ip); - t =3D ((dv * 0x1824429d) >> (32 - D_BITS)) & D_MASK; - m_pos =3D in + dict[t]; - dict[t] =3D (lzo_dict_t) (ip - in); - if (unlikely(dv !=3D get_unaligned_le32(m_pos))) - goto literal; + + if (dv =3D=3D 0) { + const unsigned char *ir =3D ip + 4; + const unsigned char *limit =3D ip_end + < (ip + MAX_ZERO_RUN_LENGTH + 1) + ? ip_end : ip + MAX_ZERO_RUN_LENGTH + 1; +#if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) && \ + defined(LZO_FAST_64BIT_MEMORY_ACCESS) + u64 dv64; + + for (; (ir + 32) <=3D limit; ir +=3D 32) { + dv64 =3D get_unaligned((u64 *)ir); + dv64 |=3D get_unaligned((u64 *)ir + 1); + dv64 |=3D get_unaligned((u64 *)ir + 2); + dv64 |=3D get_unaligned((u64 *)ir + 3); + if (dv64) + break; + } + for (; (ir + 8) <=3D limit; ir +=3D 8) { + dv64 =3D get_unaligned((u64 *)ir); + if (dv64) { +# if defined(__LITTLE_ENDIAN) + ir +=3D __builtin_ctzll(dv64) >> 3; +# elif defined(__BIG_ENDIAN) + ir +=3D __builtin_clzll(dv64) >> 3; +# else +# error "missing endian definition" +# endif + break; + } + } +#else + while ((ir < (const unsigned char *) + ALIGN((uintptr_t)ir, 4)) && + (ir < limit) && (*ir =3D=3D 0)) + ir++; + for (; (ir + 4) <=3D limit; ir +=3D 4) { + dv =3D *((u32 *)ir); + if (dv) { +# if defined(__LITTLE_ENDIAN) + ir +=3D __builtin_ctz(dv) >> 3; +# elif defined(__BIG_ENDIAN) + ir +=3D __builtin_clz(dv) >> 3; +# else +# error "missing endian definition" +# endif + break; + } + } +#endif + while (likely(ir < limit) && unlikely(*ir =3D=3D 0)) + ir++; + run_length =3D ir - ip; + if (run_length > MAX_ZERO_RUN_LENGTH) + run_length =3D MAX_ZERO_RUN_LENGTH; + } else { + t =3D ((dv * 0x1824429d) >> (32 - D_BITS)) & D_MASK; + m_pos =3D in + dict[t]; + dict[t] =3D (lzo_dict_t) (ip - in); + if (unlikely(dv !=3D get_unaligned_le32(m_pos))) + goto literal; + } =20 ii -=3D ti; ti =3D 0; t =3D ip - ii; if (t !=3D 0) { if (t <=3D 3) { - op[-2] |=3D t; + op[*state_offset] |=3D t; COPY4(op, ii); op +=3D t; } else if (t <=3D 16) { @@ -86,6 +144,17 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_= len, } } =20 + if (unlikely(run_length)) { + ip +=3D run_length; + run_length -=3D MIN_ZERO_RUN_LENGTH; + put_unaligned_le32((run_length << 21) | 0xfffc18 + | (run_length & 0x7), op); + op +=3D 4; + run_length =3D 0; + *state_offset =3D -3; + goto finished_writing_instruction; + } + m_len =3D 4; { #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) && defined(LZO_USE_CTZ= 64) @@ -168,7 +237,6 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_= len, =20 m_off =3D ip - m_pos; ip +=3D m_len; - ii =3D ip; if (m_len <=3D M2_MAX_LEN && m_off <=3D M2_MAX_OFFSET) { m_off -=3D 1; *op++ =3D (((m_len - 1) << 5) | ((m_off & 7) << 2)); @@ -205,6 +273,9 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_= len, *op++ =3D (m_off << 2); *op++ =3D (m_off >> 6); } + *state_offset =3D -2; +finished_writing_instruction: + ii =3D ip; goto next; } *out_len =3D op - out; @@ -219,6 +290,12 @@ int lzo1x_1_compress(const unsigned char *in, size_t i= n_len, unsigned char *op =3D out; size_t l =3D in_len; size_t t =3D 0; + signed char state_offset =3D -2; + + // LZO v0 will never write 17 as first byte, + // so this is used to version the bitstream + *op++ =3D 17; + *op++ =3D LZO_VERSION; =20 while (l > 20) { size_t ll =3D l <=3D (M4_MAX_OFFSET + 1) ? l : (M4_MAX_OFFSET + 1); @@ -227,7 +304,8 @@ int lzo1x_1_compress(const unsigned char *in, size_t in= _len, break; BUILD_BUG_ON(D_SIZE * sizeof(lzo_dict_t) > LZO1X_1_MEM_COMPRESS); memset(wrkmem, 0, D_SIZE * sizeof(lzo_dict_t)); - t =3D lzo1x_1_do_compress(ip, ll, op, out_len, t, wrkmem); + t =3D lzo1x_1_do_compress(ip, ll, op, out_len, + t, wrkmem, &state_offset); ip +=3D ll; op +=3D *out_len; l -=3D ll; @@ -240,7 +318,7 @@ int lzo1x_1_compress(const unsigned char *in, size_t in= _len, if (op =3D=3D out && t <=3D 238) { *op++ =3D (17 + t); } else if (t <=3D 3) { - op[-2] |=3D t; + op[state_offset] |=3D t; } else if (t <=3D 18) { *op++ =3D (t - 3); } else { diff --git a/lib/lzo/lzo1x_decompress_safe.c b/lib/lzo/lzo1x_decompress_saf= e.c index aa95d3066b7d..b8f88d5ea3ff 100644 --- a/lib/lzo/lzo1x_decompress_safe.c +++ b/lib/lzo/lzo1x_decompress_safe.c @@ -46,11 +46,23 @@ int lzo1x_decompress_safe(const unsigned char *in, size= _t in_len, const unsigned char * const ip_end =3D in + in_len; unsigned char * const op_end =3D out + *out_len; =20 + unsigned char bitstream_version; + op =3D out; ip =3D in; =20 if (unlikely(in_len < 3)) goto input_overrun; + + if (likely(*ip =3D=3D 17)) { + bitstream_version =3D ip[1]; + ip +=3D 2; + if (unlikely(in_len < 5)) + goto input_overrun; + } else { + bitstream_version =3D 0; + } + if (*ip > 17) { t =3D *ip++ - 17; if (t < 4) { @@ -151,32 +163,49 @@ int lzo1x_decompress_safe(const unsigned char *in, si= ze_t in_len, m_pos -=3D next >> 2; next &=3D 3; } else { - m_pos =3D op; - m_pos -=3D (t & 8) << 11; - t =3D (t & 7) + (3 - 1); - if (unlikely(t =3D=3D 2)) { - size_t offset; - const unsigned char *ip_last =3D ip; + NEED_IP(2); + next =3D get_unaligned_le16(ip); + if (((next & 0xfffc) =3D=3D 0xfffc) && + ((t & 0xf8) =3D=3D 0x18) && + likely(bitstream_version)) { + NEED_IP(3); + t &=3D 7; + t |=3D ip[2] << 3; + t +=3D MIN_ZERO_RUN_LENGTH; + NEED_OP(t); + memset(op, 0, t); + op +=3D t; + next &=3D 3; + ip +=3D 3; + goto match_next; + } else { + m_pos =3D op; + m_pos -=3D (t & 8) << 11; + t =3D (t & 7) + (3 - 1); + if (unlikely(t =3D=3D 2)) { + size_t offset; + const unsigned char *ip_last =3D ip; =20 - while (unlikely(*ip =3D=3D 0)) { - ip++; - NEED_IP(1); - } - offset =3D ip - ip_last; - if (unlikely(offset > MAX_255_COUNT)) - return LZO_E_ERROR; + while (unlikely(*ip =3D=3D 0)) { + ip++; + NEED_IP(1); + } + offset =3D ip - ip_last; + if (unlikely(offset > MAX_255_COUNT)) + return LZO_E_ERROR; =20 - offset =3D (offset << 8) - offset; - t +=3D offset + 7 + *ip++; - NEED_IP(2); + offset =3D (offset << 8) - offset; + t +=3D offset + 7 + *ip++; + NEED_IP(2); + next =3D get_unaligned_le16(ip); + } + ip +=3D 2; + m_pos -=3D next >> 2; + next &=3D 3; + if (m_pos =3D=3D op) + goto eof_found; + m_pos -=3D 0x4000; } - next =3D get_unaligned_le16(ip); - ip +=3D 2; - m_pos -=3D next >> 2; - next &=3D 3; - if (m_pos =3D=3D op) - goto eof_found; - m_pos -=3D 0x4000; } TEST_LB(m_pos); #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS) diff --git a/lib/lzo/lzodefs.h b/lib/lzo/lzodefs.h index 06fa83a38e0a..682359058b3c 100644 --- a/lib/lzo/lzodefs.h +++ b/lib/lzo/lzodefs.h @@ -13,6 +13,12 @@ */ =20 =20 +/* Version + * 0: original lzo version + * 1: lzo with support for RLE + */ +#define LZO_VERSION 1 + #define COPY4(dst, src) \ put_unaligned(get_unaligned((const u32 *)(src)), (u32 *)(dst)) #if defined(CONFIG_X86_64) || defined(CONFIG_ARM64) @@ -31,6 +37,7 @@ #elif defined(CONFIG_X86_64) || defined(CONFIG_ARM64) #define LZO_USE_CTZ64 1 #define LZO_USE_CTZ32 1 +#define LZO_FAST_64BIT_MEMORY_ACCESS #elif defined(CONFIG_X86) || defined(CONFIG_PPC) #define LZO_USE_CTZ32 1 #elif defined(CONFIG_ARM) @@ -45,7 +52,7 @@ #define M1_MAX_OFFSET 0x0400 #define M2_MAX_OFFSET 0x0800 #define M3_MAX_OFFSET 0x4000 -#define M4_MAX_OFFSET 0xbfff +#define M4_MAX_OFFSET 0xbffe =20 #define M1_MIN_LEN 2 #define M1_MAX_LEN 2 @@ -61,6 +68,9 @@ #define M3_MARKER 32 #define M4_MARKER 16 =20 +#define MIN_ZERO_RUN_LENGTH 4 +#define MAX_ZERO_RUN_LENGTH (2047 + MIN_ZERO_RUN_LENGTH) + #define lzo_dict_t unsigned short #define D_BITS 13 #define D_SIZE (1u << D_BITS) --=20 2.17.1