From nobody Sat Apr 11 19:52:29 2026 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 8FCC5C19F2D for ; Sat, 6 Aug 2022 16:25:35 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232860AbiHFQZd (ORCPT ); Sat, 6 Aug 2022 12:25:33 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47832 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232621AbiHFQZa (ORCPT ); Sat, 6 Aug 2022 12:25:30 -0400 Received: from mail-pl1-x62c.google.com (mail-pl1-x62c.google.com [IPv6:2607:f8b0:4864:20::62c]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 171BCF5B4 for ; Sat, 6 Aug 2022 09:25:26 -0700 (PDT) Received: by mail-pl1-x62c.google.com with SMTP id w10so5162339plq.0 for ; Sat, 06 Aug 2022 09:25:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc; bh=UbGxgyfmTUw0NnY5/Pu/ELaJtqQmXlFiXmZPB/RD9VQ=; b=HkHVd3hlXKYP2R+Mk2Pd6mQCloOY1m4EmdMyhrH26cSEUUAiV2mnYf+zdC8MVUqkTP oxASsq1/rht3Ub3fKW+wJRv8oyY/QmeZ0DcOW6KR6SUv5FurMf8OdMr0sLjOXxMTzzXa r5HnPCO2dkvKZ0SV8yiZfMjZVLzBGgmKj7FJN7Su1wqcXggFr3kVsKTHL8Em03nVYOAf /rJadZIvC8REvQxEEeUTDFcqVMb2t1rPLdpFuWBhgiH8GkYrlcaSvspoQ2vyKNGgKTeY PmfrxKA6c6Lh0vENmq5pAud2L7vENuXpOglTWDlCIUEHGzSY/bow6AiP+pSs+6ZLagJ9 lEXA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc; bh=UbGxgyfmTUw0NnY5/Pu/ELaJtqQmXlFiXmZPB/RD9VQ=; b=JBWrwYD+nAdA92pPXqZwmu4GDs22SY+PgPf/rVGtEKovOeA7ml+CndaOeiYggZcd7P h7m23P177Dn2H+FH2jinto4gMbgxmEacMJ+xQVYCkG0zTimyBbLYe3AksfN0wvbuCBtm qSIn1TndTWiRJpd/YsmChohPpd5SrKd4VF5B3+GIKsMY1BoIRrqXubs9zNgNlirnkSaB 3+5186IooAm7qYG0YS0LV0vERB/bbsCYxHB4KplZfYZVn+jGmvNiKJpTvc1lcPJ241Ce WgeFkaHyY2et3AM90ExsKeX9TkgLx1RFqZiK84/RgCG/Vu6F0IHXIkeCmSMk5ncsYIR/ YOSQ== X-Gm-Message-State: ACgBeo2l22tf9VJl7IRmUBdhE5QO6+xPO3uHyh8Njpi5AEvxwj0ORHKt mZMQGk53/uOKixM/lGkEFrYxcbyI25DamA== X-Google-Smtp-Source: AA6agR5yVyVKy+WlmRPtgWkf0lsgZfGXMX54t/jfTMb09y973IKoLoy5hBWIn0eoel118MLO+t+QMQ== X-Received: by 2002:a17:902:be16:b0:170:8ebf:204c with SMTP id r22-20020a170902be1600b001708ebf204cmr3102308pls.47.1659803125608; Sat, 06 Aug 2022 09:25:25 -0700 (PDT) Received: from localhost.localdomain (ec2-13-113-80-70.ap-northeast-1.compute.amazonaws.com. [13.113.80.70]) by smtp.gmail.com with ESMTPSA id s1-20020a17090a2f0100b001f04479017fsm4990927pjd.29.2022.08.06.09.25.23 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 06 Aug 2022 09:25:25 -0700 (PDT) From: Zhang Boyang To: Thomas Gleixner , Ferdinand Blomqvist , linux-kernel@vger.kernel.org Cc: Kees Cook , Randy Dunlap , Zhang Boyang Subject: [PATCH RESEND V3 1/6] rslib: Fix incorrect documentation of rs_modnn() Date: Sun, 7 Aug 2022 00:25:05 +0800 Message-Id: <20220806162510.157196-2-zhangboyang.id@gmail.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20220806162510.157196-1-zhangboyang.id@gmail.com> References: <20220806162510.157196-1-zhangboyang.id@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" Previous documentation of rs_modnn() states simple arithmetic modulo return a wrong result for values >=3D (3 * rs->nn). However, that is not true. The rs_modnn() does the exactly same job as (x % rs->nn). This can be proved from following loop invariants: while (x >=3D rs->nn) { x -=3D rs->nn; // (1) x =3D (x >> rs->mm) + (x & rs->nn); // (2) } Let x0 denote the value of x before assignment. At (1), it is obvious that x % nn =3D=3D x0 % nn. At (2), because nn =3D=3D ((1 << mm) - 1), we h= ave x0 % nn =3D=3D x0 % nn x0 % nn =3D=3D (((x0 >> mm) << mm) + (x0 & nn)) % nn x0 % nn =3D=3D ((x0 >> mm) * (nn + 1) + (x0 & nn)) % nn x0 % nn =3D=3D ((x0 >> mm) * ((nn + 1) % nn) + (x0 & nn)) % nn x0 % nn =3D=3D ((x0 >> mm) * 1 + (x0 & nn)) % nn // let's assume nn > 1 x0 % nn =3D=3D ((x0 >> mm) + (x0 & nn)) % nn x0 % nn =3D=3D x % nn When the loop exits, it is obvious that 0 <=3D x < nn, so the return value must equal to (x % rs->nn). Signed-off-by: Zhang Boyang --- include/linux/rslib.h | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) diff --git a/include/linux/rslib.h b/include/linux/rslib.h index 238bb85243d3..507fa14c03b2 100644 --- a/include/linux/rslib.h +++ b/include/linux/rslib.h @@ -116,8 +116,7 @@ void free_rs(struct rs_control *rs); * rs->mm =3D number of bits per symbol * rs->nn =3D (2^rs->mm) - 1 * - * Simple arithmetic modulo would return a wrong result for values - * >=3D 3 * rs->nn + * Calculate (x % rs->nn), without using a div instruction */ static inline int rs_modnn(struct rs_codec *rs, int x) { --=20 2.30.2 From nobody Sat Apr 11 19:52:29 2026 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 9CE56C25B06 for ; Sat, 6 Aug 2022 16:25:48 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233215AbiHFQZk (ORCPT ); Sat, 6 Aug 2022 12:25:40 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47846 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232679AbiHFQZb (ORCPT ); Sat, 6 Aug 2022 12:25:31 -0400 Received: from mail-pj1-x102f.google.com (mail-pj1-x102f.google.com [IPv6:2607:f8b0:4864:20::102f]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 307E11057E for ; Sat, 6 Aug 2022 09:25:28 -0700 (PDT) Received: by mail-pj1-x102f.google.com with SMTP id v16-20020a17090abb9000b001f25244c65dso10866178pjr.2 for ; Sat, 06 Aug 2022 09:25:28 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc; bh=4akhw7wybTZyWH6tXqtxZK6m2uwvnVK6i/fg5yqCKis=; b=b8XPMJIr1Kgg2dGOR27KlaTRLM6gL2PtCzD8IXcknbeGsz3gpmRwYrbnHeoPbXHdKJ pq7nB331ZAfrtXut6OVMWX9YoyQRS/T12bwSQKUZeSIILBNSApUxhEYJAVkyzf+VP1qk WE8W20fP4FenpD+BZTqIshUyvkkuyz88iT8HNCr+vjj3phUc96mpqfl2/crG2LfROiDU NK/mUbws2tlZMyUr9QbjxfXh2JPH5+o4wB7UlHOmxGZPk7o9Ufn+9y6j3E3HiOmSOKHa fswC+7ZzDFQoY5qK3V9AQqzLBmOThd/UxcHRMpSfJ3use8RBL/Q/hW8NFSCTZvO3RVQh MI6Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc; bh=4akhw7wybTZyWH6tXqtxZK6m2uwvnVK6i/fg5yqCKis=; b=ooyFp3DVKIwNR2xXkOiq8HhvTYp5dMRu6M5Y9Qxady2lkUPQgi0zaixG5ZVMOcOZZk 7sTWii8ea0Gyd248il82CjeLP+OEMC7bngTYkJdP0fmyxfa5AjZ3n/u8K/0ZbuiemxXI 77STDEQTuGXS+Jgnboa5f3nMHdlC6rKQ2Pu56AkqiMGlGTLwp3ZQgXgAbQ7jSFeRMta0 A4Qg2MbyGSdfuW6b7Ee4Zt1k/7HZfV2oYXy3gbuN7e6BFkQM4ItnRPiFb27v6Uj70ch0 qv6emZWVzBKCkTnsLmlQkvmQ9yMca/zGCtxsrpvWlSZ/ry7tDSzDOzVu+0uMZpsUmi1r LKfw== X-Gm-Message-State: ACgBeo3jBXh/Bz+1rlzCv4cZbjZCiaTTJoYb9nUcIf7QCE+7PlVW7yuH GY/COWJ5M3ztSNAIHnSGtRQ= X-Google-Smtp-Source: AA6agR4BIqC1PUplAkI53wIgGR2625Bz1/VUZPxTPdKi5KO5/d1J+mh6UKd1lZWifzbCSvXXkG3sOg== X-Received: by 2002:a17:903:40c4:b0:16d:d2a9:43ae with SMTP id t4-20020a17090340c400b0016dd2a943aemr11525195pld.57.1659803128418; Sat, 06 Aug 2022 09:25:28 -0700 (PDT) Received: from localhost.localdomain (ec2-13-113-80-70.ap-northeast-1.compute.amazonaws.com. [13.113.80.70]) by smtp.gmail.com with ESMTPSA id s1-20020a17090a2f0100b001f04479017fsm4990927pjd.29.2022.08.06.09.25.25 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 06 Aug 2022 09:25:28 -0700 (PDT) From: Zhang Boyang To: Thomas Gleixner , Ferdinand Blomqvist , linux-kernel@vger.kernel.org Cc: Kees Cook , Randy Dunlap , Zhang Boyang Subject: [PATCH RESEND V3 2/6] rslib: Replace hard-coded 1 with alpha_to[0] Date: Sun, 7 Aug 2022 00:25:06 +0800 Message-Id: <20220806162510.157196-3-zhangboyang.id@gmail.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20220806162510.157196-1-zhangboyang.id@gmail.com> References: <20220806162510.157196-1-zhangboyang.id@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" Currently the rslib allows customizing the finite field by the `gffunc' parameter of init_rs_non_canonical(). However, there are several places in rslib use hard-coded 1 instead of alpha_to[0], leading to errors if gffunc(0) !=3D 1. This patch fixes the problem. One of such `gffunc' might be gffunc'(x) =3D swab16(gffunc(swab16(x))), as gffunc'(0) =3D swab16(1). This special gffunc'(x) is useful when implementing RS coder for 16 bit foreign-endian symbols. Signed-off-by: Zhang Boyang --- lib/reed_solomon/decode_rs.c | 4 ++-- lib/reed_solomon/reed_solomon.c | 4 ++-- 2 files changed, 4 insertions(+), 4 deletions(-) diff --git a/lib/reed_solomon/decode_rs.c b/lib/reed_solomon/decode_rs.c index 805de84ae83d..6c1d53d1b702 100644 --- a/lib/reed_solomon/decode_rs.c +++ b/lib/reed_solomon/decode_rs.c @@ -104,7 +104,7 @@ =20 decode: memset(&lambda[1], 0, nroots * sizeof(lambda[0])); - lambda[0] =3D 1; + lambda[0] =3D alpha_to[0]; =20 if (no_eras > 0) { /* Init lambda to be the erasure locator polynomial */ @@ -198,7 +198,7 @@ memcpy(®[1], &lambda[1], nroots * sizeof(reg[0])); count =3D 0; /* Number of roots of lambda(x) */ for (i =3D 1, k =3D iprim - 1; i <=3D nn; i++, k =3D rs_modnn(rs, k + ipr= im)) { - q =3D 1; /* lambda[0] is always 0 */ + q =3D alpha_to[0]; /* lambda[0] is always 0 */ for (j =3D deg_lambda; j > 0; j--) { if (reg[j] !=3D nn) { reg[j] =3D rs_modnn(rs, reg[j] + j); diff --git a/lib/reed_solomon/reed_solomon.c b/lib/reed_solomon/reed_solomo= n.c index bbc01bad3053..bb4f44c8edba 100644 --- a/lib/reed_solomon/reed_solomon.c +++ b/lib/reed_solomon/reed_solomon.c @@ -131,9 +131,9 @@ static struct rs_codec *codec_init(int symsize, int gfp= oly, int (*gffunc)(int), rs->iprim =3D iprim / prim; =20 /* Form RS code generator polynomial from its roots */ - rs->genpoly[0] =3D 1; + rs->genpoly[0] =3D rs->alpha_to[0]; for (i =3D 0, root =3D fcr * prim; i < nroots; i++, root +=3D prim) { - rs->genpoly[i + 1] =3D 1; + rs->genpoly[i + 1] =3D rs->alpha_to[0]; /* Multiply rs->genpoly[] by @**(root + x) */ for (j =3D i; j > 0; j--) { if (rs->genpoly[j] !=3D 0) { --=20 2.30.2 From nobody Sat Apr 11 19:52:29 2026 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 23C43C19F2D for ; Sat, 6 Aug 2022 16:25:49 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233435AbiHFQZo (ORCPT ); Sat, 6 Aug 2022 12:25:44 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47904 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232878AbiHFQZd (ORCPT ); Sat, 6 Aug 2022 12:25:33 -0400 Received: from mail-pf1-x434.google.com (mail-pf1-x434.google.com [IPv6:2607:f8b0:4864:20::434]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 2570411457 for ; Sat, 6 Aug 2022 09:25:32 -0700 (PDT) Received: by mail-pf1-x434.google.com with SMTP id f28so4737837pfk.1 for ; Sat, 06 Aug 2022 09:25:32 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc; bh=Tlr/PaqbxkpfKuux+ZeYdthv16cbtlg5RBXZEsNXtGw=; b=Mn+5qAQtoswA528bAeJwnZfGXmUf3wXZiCtGaiNazI8Xqczs3yY10dq/W7sMOYjAfJ NO7KYhT2nYfV0xByuSTfyCHOWsPeMjUleWaHlDX8JYMi6ZRwtMMVJDHrowG04BxfNKEi O+pymlw5q6lrPn8TzpvkGnH4iQEJQjEVN8q1NL++Bu05CmaN59TN/2QrUnmUsWJUuY7l SvbQ1mkGfIqQ7K4oNQ2YQzF8Gr44HI5GrcKe7ZqJOLVd3FQ2BRoMMWkMBTreo41gMXrz Q2x1BLZcWXZJftwR0dKlDGDRtTtQrr+y5o+QXj2uRJtcffd1CV02PAFVDmLjSn6bF+T7 3rng== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc; bh=Tlr/PaqbxkpfKuux+ZeYdthv16cbtlg5RBXZEsNXtGw=; b=PwOER3YuA4qL3ZpM8Mmjki629Li9NldJgU0+MxBxachasOCeH0r97Z+De+4vDcuucS lXdtCaa9iroJSNKfttBJ7dxjZqwnGCB0Tf6ZxLFbalhOk5/yFfdJyXG712wGQ2CX5PyT McFnLGBIfgrswTXSimDObR2DAZDojuzRnrZ+Z44Ig69nXtUIx9McPhf3qvTORCHgbI0t PtoBEGEOklBJXvoQbGIkGAkNsQmmVD90Xatmo5z/SvLVrUSVLgHI2Q8p6YSyuNnwRoGC IcHfWGeJyd2EcAaPlrcnvwmMfACmSnRF00jY21epaasFt7wO92sxv8tdRziC+PiR9qRw niqg== X-Gm-Message-State: ACgBeo1WI02BZtz+MaVDsFpkNc3cSHqrkK8/xvPZF7m9nJV8eC782iOL Ak7YGmEnJUGPup09O4hewOM= X-Google-Smtp-Source: AA6agR6scjUmAyGOnOVRExK9PxzftY+DxlzyKN/lR+WECWZVYdxE6FD4KvF6yE9ORQT5sqbN5DnFCQ== X-Received: by 2002:a05:6a00:2392:b0:52e:b4fb:848 with SMTP id f18-20020a056a00239200b0052eb4fb0848mr8705112pfc.8.1659803131495; Sat, 06 Aug 2022 09:25:31 -0700 (PDT) Received: from localhost.localdomain (ec2-13-113-80-70.ap-northeast-1.compute.amazonaws.com. [13.113.80.70]) by smtp.gmail.com with ESMTPSA id s1-20020a17090a2f0100b001f04479017fsm4990927pjd.29.2022.08.06.09.25.28 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 06 Aug 2022 09:25:31 -0700 (PDT) From: Zhang Boyang To: Thomas Gleixner , Ferdinand Blomqvist , linux-kernel@vger.kernel.org Cc: Kees Cook , Randy Dunlap , Zhang Boyang Subject: [PATCH RESEND V3 3/6] rslib: Fix obvious documentation mistakes Date: Sun, 7 Aug 2022 00:25:07 +0800 Message-Id: <20220806162510.157196-4-zhangboyang.id@gmail.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20220806162510.157196-1-zhangboyang.id@gmail.com> References: <20220806162510.157196-1-zhangboyang.id@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" This patch fixes some obvious documentation mistakes. Signed-off-by: Zhang Boyang --- include/linux/rslib.h | 4 ++-- lib/reed_solomon/reed_solomon.c | 2 +- 2 files changed, 3 insertions(+), 3 deletions(-) diff --git a/include/linux/rslib.h b/include/linux/rslib.h index 507fa14c03b2..cd0b5a7a5698 100644 --- a/include/linux/rslib.h +++ b/include/linux/rslib.h @@ -19,8 +19,8 @@ * * @mm: Bits per symbol * @nn: Symbols per block (=3D (1< X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id A98D0C19F2D for ; Sat, 6 Aug 2022 16:25:55 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233390AbiHFQZx (ORCPT ); Sat, 6 Aug 2022 12:25:53 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47944 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232893AbiHFQZf (ORCPT ); Sat, 6 Aug 2022 12:25:35 -0400 Received: from mail-pg1-x52b.google.com (mail-pg1-x52b.google.com [IPv6:2607:f8b0:4864:20::52b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 9C36011461 for ; Sat, 6 Aug 2022 09:25:34 -0700 (PDT) Received: by mail-pg1-x52b.google.com with SMTP id s206so5104741pgs.3 for ; Sat, 06 Aug 2022 09:25:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc; bh=FpRML5FM7z0q20RyQQ3Ksaz1Bp1mVVRpaiFCWoESebI=; b=SYK4ZlgIr9eRjmImdozBr1Er95Hpb183FLl1WmZOoT/hmx1oznn4IEH+4sZgTsITDe Jbbu8iWKh61Z3o19R3jNU30AOlf/7mkIHa5NoprcmKIBA2geuRGt4Ssuqi83T2FMNi1M /oT5Ys/zOXkuWTaXajq76Wlyd39Sg50TxBrGvPfACYej1WV1F8bc+ow3111dTGpZy/vl borTfKp//mA/v6GzRnAqQ3v8tXMbbJqsEnlrQQQ/mO7QcYy6Zphbh+wHtR0/0XH3960c ySXPNwgaqtIEOqGbLJltYARNPabPNIEW9zs2Hjv1ylJAjBB9XO0OtMVqevNj1LejCsEe SfyQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc; bh=FpRML5FM7z0q20RyQQ3Ksaz1Bp1mVVRpaiFCWoESebI=; b=xC4/wqCpxfpeuMVPeC9Zlwp5Jl96lK7Lr3ir8FjvQNa3MwjYSklIibGDDDFmwMn5qO hzYBSN80+k8jhUpGdGr66YYYBiTXt/TaOuw1M928iqMUI52flWqzIby8utVbVhGdRNXN 4ckGLIL+ZGuwQM+qFbYJhP0Bdd0INKGgfGt5miPgzBfs2597KA/Jbee901NQGnWXvGZv ELRDhWRX2jLWcNqi9uu6shQTsPNNNGtRDnTDB6HOl0Vuh8l+q9fQZkPDCMyuImgNG39N oYPo0sDOgCiZembuc//YOqhO/IS1SOQ7eDYhq2iR6qwwPi9NczrZfXCtmGnX7z14QvJI 7lbA== X-Gm-Message-State: ACgBeo2fWtZZD8TXRnZ5qTNeFSLR1683kbEeSXTfifaaN981WyolfTka xqEPUI4VfRms/vNbqaD8BsI= X-Google-Smtp-Source: AA6agR6F32DLoFeS/le46RtJyB6ofXPLEFyPdCXRVyFSziywcYwNA6QpmRdZvjdLoGIdkJX7pUgh3w== X-Received: by 2002:a05:6a00:2190:b0:52b:fe5f:5939 with SMTP id h16-20020a056a00219000b0052bfe5f5939mr12039594pfi.83.1659803134119; Sat, 06 Aug 2022 09:25:34 -0700 (PDT) Received: from localhost.localdomain (ec2-13-113-80-70.ap-northeast-1.compute.amazonaws.com. [13.113.80.70]) by smtp.gmail.com with ESMTPSA id s1-20020a17090a2f0100b001f04479017fsm4990927pjd.29.2022.08.06.09.25.31 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 06 Aug 2022 09:25:33 -0700 (PDT) From: Zhang Boyang To: Thomas Gleixner , Ferdinand Blomqvist , linux-kernel@vger.kernel.org Cc: Kees Cook , Randy Dunlap , Zhang Boyang Subject: [PATCH RESEND V3 4/6] rslib: Fix kernel-doc style for rs_modnn() Date: Sun, 7 Aug 2022 00:25:08 +0800 Message-Id: <20220806162510.157196-5-zhangboyang.id@gmail.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20220806162510.157196-1-zhangboyang.id@gmail.com> References: <20220806162510.157196-1-zhangboyang.id@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" This patch fixes the style of kernel-doc of rs_modnn(). Signed-off-by: Zhang Boyang Reviewed-by: Randy Dunlap --- include/linux/rslib.h | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/include/linux/rslib.h b/include/linux/rslib.h index cd0b5a7a5698..e92923fff3bc 100644 --- a/include/linux/rslib.h +++ b/include/linux/rslib.h @@ -107,7 +107,8 @@ struct rs_control *init_rs_non_canonical(int symsize, i= nt (*func)(int), /* Release a rs control structure */ void free_rs(struct rs_control *rs); =20 -/** modulo replacement for galois field arithmetics +/** + * rs_modnn() - Modulo replacement for galois field arithmetics * * @rs: Pointer to the RS codec * @x: the value to reduce --=20 2.30.2 From nobody Sat Apr 11 19:52:29 2026 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 724F7C19F2D for ; Sat, 6 Aug 2022 16:26:01 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233338AbiHFQZ6 (ORCPT ); Sat, 6 Aug 2022 12:25:58 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47880 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233018AbiHFQZj (ORCPT ); Sat, 6 Aug 2022 12:25:39 -0400 Received: from mail-pf1-x42b.google.com (mail-pf1-x42b.google.com [IPv6:2607:f8b0:4864:20::42b]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 9885E11838 for ; Sat, 6 Aug 2022 09:25:37 -0700 (PDT) Received: by mail-pf1-x42b.google.com with SMTP id k14so2700370pfh.0 for ; Sat, 06 Aug 2022 09:25:37 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc; bh=FEKEneG+vJbEcnlCaC2oiLWn9YgUu5T0FQV2Cn/dZ9U=; b=gbSqz1N2qexfCCS3+eMv4LMN2uAn8OTwBgUKZwyrBVcaMcZ+VPs0IBPIo6p6Jt82tV qRtVtsb3+EkTw2NDSwSWIUKgLcmn21KCZzi0U5cHpgqIlLHOG4RNDkoFY6525uzRKgWU G35Ou+yBu4oHnzbYRGjY+6X80iUo3w1GnKDwY6pS7XHvM3eeHFSwDpkMf661EduDaFIN rvU0lqQjgXdO9FHSLlAFf8s/QmJmUs3mp02OoPDg2zSEpfYU+kyvb2FwOEUMgIO1n4Pq GtvozFYvtHqUOveC9KSnXq9Z9FQXBe/arVb1BW9LqIu26adz8OGO7K2NctpBT3Pqxw+R 9WbQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc; bh=FEKEneG+vJbEcnlCaC2oiLWn9YgUu5T0FQV2Cn/dZ9U=; b=Tkdrvvrim+7ssopRJCH1abNC71a7q+QGgMG2nrpMP7FQ5n221OlVV1phTZh/E4TPIE WbTlt/P2uHRY1JdPBFi/kQ9FjB6OhSUBXC7ReYGBZWZb1My/EdJYWhgN6g5Lc92fBPwx N+YKsueraCL0kZ/+GOULR7OEz2A0hFFO7QIBPQO5sXYuhyMdgVdJHFwklpQOp37DEVXB KBfWF35NVNoMMJgryFYG1yTTpYHKr5+VWlEdVo42rI5qrnpu/E3U1na0uY6sgmPV5eWl tYk5aC/gh48VuzINrYFKXfKY0EnbmfOJOesiRLceufQ3wUf6PGUusV3gUHVO3LUyBgjk dMLg== X-Gm-Message-State: ACgBeo3FVxMSTCRgOsk16EtCH9EPhiMIXsb/1ei1DxO7FeW/9SG/+BiW bzRajiO0DQsNzvyc5zy5das= X-Google-Smtp-Source: AA6agR6LFPxz8BS70jbuTfYeD4jvPL4TLGfjvEgiSzTwP+lyRKOiJjkLnPhJDTFpC3QKmEukRT9xNA== X-Received: by 2002:a65:57c8:0:b0:41c:fa29:ae1d with SMTP id q8-20020a6557c8000000b0041cfa29ae1dmr8213118pgr.136.1659803136890; Sat, 06 Aug 2022 09:25:36 -0700 (PDT) Received: from localhost.localdomain (ec2-13-113-80-70.ap-northeast-1.compute.amazonaws.com. [13.113.80.70]) by smtp.gmail.com with ESMTPSA id s1-20020a17090a2f0100b001f04479017fsm4990927pjd.29.2022.08.06.09.25.34 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 06 Aug 2022 09:25:36 -0700 (PDT) From: Zhang Boyang To: Thomas Gleixner , Ferdinand Blomqvist , linux-kernel@vger.kernel.org Cc: Kees Cook , Randy Dunlap , Zhang Boyang Subject: [PATCH RESEND V3 5/6] rslib: Improve the performance of encode_rs.c Date: Sun, 7 Aug 2022 00:25:09 +0800 Message-Id: <20220806162510.157196-6-zhangboyang.id@gmail.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20220806162510.157196-1-zhangboyang.id@gmail.com> References: <20220806162510.157196-1-zhangboyang.id@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" This patch enhances the performance of RS encoder by following points: 1) Avoid memmove(). The shifting operation done by memmove() can be merged into the calculation loop above. 2) Introduce rs_modnn_fast(). The original rs_modnn() contains a loop which may be slow. Since (fb + genpoly[...]) is always strictly less than (2 * rs->nn), we can use a ternary operator to do the same calculation. The new faster function is named rs_modnn_fast(). The new rs_modnn_fast(x) requires 0 <=3D x < 2*nn, in contrast, original rs_modnn(x) only requires x >=3D 0. To make things clear, the documentation of original rs_modnn() is also updated. Signed-off-by: Zhang Boyang --- include/linux/rslib.h | 15 ++++++++++++++- lib/reed_solomon/encode_rs.c | 21 ++++++++++----------- 2 files changed, 24 insertions(+), 12 deletions(-) diff --git a/include/linux/rslib.h b/include/linux/rslib.h index e92923fff3bc..a277a178157b 100644 --- a/include/linux/rslib.h +++ b/include/linux/rslib.h @@ -111,7 +111,7 @@ void free_rs(struct rs_control *rs); * rs_modnn() - Modulo replacement for galois field arithmetics * * @rs: Pointer to the RS codec - * @x: the value to reduce + * @x: x >=3D 0 ; the value to reduce * * where * rs->mm =3D number of bits per symbol @@ -128,4 +128,17 @@ static inline int rs_modnn(struct rs_codec *rs, int x) return x; } =20 +/** + * rs_modnn_fast() - Modulo replacement for galois field arithmetics + * + * @rs: Pointer to the RS codec + * @x: 0 <=3D x < 2*nn ; the value to reduce + * + * Same as rs_modnn(x), but faster, at the cost of limited value range of= @x +*/ +static inline int rs_modnn_fast(struct rs_codec *rs, int x) +{ + return x - rs->nn < 0 ? x : x - rs->nn; +} + #endif diff --git a/lib/reed_solomon/encode_rs.c b/lib/reed_solomon/encode_rs.c index 9112d46e869e..6e3847b17ad4 100644 --- a/lib/reed_solomon/encode_rs.c +++ b/lib/reed_solomon/encode_rs.c @@ -27,19 +27,18 @@ =20 for (i =3D 0; i < len; i++) { fb =3D index_of[((((uint16_t) data[i])^invmsk) & msk) ^ par[0]]; - /* feedback term is non-zero */ if (fb !=3D nn) { - for (j =3D 1; j < nroots; j++) { - par[j] ^=3D alpha_to[rs_modnn(rs, fb + - genpoly[nroots - j])]; - } - } - /* Shift */ - memmove(&par[0], &par[1], sizeof(uint16_t) * (nroots - 1)); - if (fb !=3D nn) { - par[nroots - 1] =3D alpha_to[rs_modnn(rs, - fb + genpoly[0])]; + /* feedback term is non-zero */ + for (j =3D 1; j < nroots; j++) + par[j - 1] =3D par[j] ^ alpha_to[rs_modnn_fast(rs, + fb + + genpoly[nroots - j])]; + par[nroots - 1] =3D alpha_to[rs_modnn_fast(rs, + fb + + genpoly[0])]; } else { + for (j =3D 1; j < nroots; j++) + par[j - 1] =3D par[j]; par[nroots - 1] =3D 0; } } --=20 2.30.2 From nobody Sat Apr 11 19:52:29 2026 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 53EE7C19F2D for ; Sat, 6 Aug 2022 16:26:08 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233583AbiHFQ0G (ORCPT ); Sat, 6 Aug 2022 12:26:06 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:47846 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232679AbiHFQZl (ORCPT ); Sat, 6 Aug 2022 12:25:41 -0400 Received: from mail-pf1-x42d.google.com (mail-pf1-x42d.google.com [IPv6:2607:f8b0:4864:20::42d]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 5AC131115A for ; Sat, 6 Aug 2022 09:25:40 -0700 (PDT) Received: by mail-pf1-x42d.google.com with SMTP id b133so4719107pfb.6 for ; Sat, 06 Aug 2022 09:25:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc; bh=N1BCvou7NjHgyn5FaZtbtm6KuJ8J4dRe9ttSN/j/ctQ=; b=VJzvGIIL2+vKbZhL3bMehx1UkSKnh+x7IntHakUkAlrZV4c5h1YCr9iolr1AJJf9z1 VHnmZ2rg0h6A/fGZ5Wg80jP4ZlkSWKaQ5Sv8DpDQ6/tDRKJuauTvDuA0VNZ/m7U2hKTd 3UX0ZZfTi4QgrS81gulr4Dv6sihDZj+u9EZTnNYyIvWWLszi50sfmwUpqxwYPk8m4qBK bbJSMZzEqrOlsmWWpNvBm6hqSdYSg0htZH5XKWJrF/XIpjg3iWgP2v6UzI/JgSFyeJZy 9Ce4nApaqLsR8wMDPKnxemX9X7BeoAZWXjlS1pPhMa/aRYB26ayWPZl4DmL/AkqTOE6A O9uw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc; bh=N1BCvou7NjHgyn5FaZtbtm6KuJ8J4dRe9ttSN/j/ctQ=; b=3lqWKijsHNxXuARgY/3HF/fwwPiF31VxDHL3BnQChSkXbMjAjRypF2eprVUTVmr7Nj zzdpSRN1ZzloNIVcKNAFcqAGVaCOQQMXsGqpquMeNmONH8auNYqJ87tG1zO+FHiUbz5o WLff4sezno6+eqkmzoKDmKJFlPHw2RGwS2IA+PHIBPKRusOATAnxJx/dcoC0PrxUQr03 aGKVMFYPpDAOOKfoDOFZ+s25h3IEu625KfER0g2vUrTZcWiYYOEBojfmzJ6F0L8km+8l WwIgRzAwLeyH+IZUBJirnEV3Xq1U6/G4NAxiB1rEPYq17PrtI9xxKNwPMaiH9ALHwME+ n8kg== X-Gm-Message-State: ACgBeo3t57PslT7ZTiRWM7Mwk+Yj0k5mk5c45dkuXXzVMcvERt1FeZ+4 pf0K1mbcM/5GCxIUQsQuzaY= X-Google-Smtp-Source: AA6agR6DthDFW99OTxtafIz9oHu+1QpBzLnGT2aZvsj4qAzL5uzEmEYTwOTEyg+JBaEpcN5UCoSr0Q== X-Received: by 2002:a05:6a00:813:b0:52e:c38f:f2cf with SMTP id m19-20020a056a00081300b0052ec38ff2cfmr7680611pfk.57.1659803139780; Sat, 06 Aug 2022 09:25:39 -0700 (PDT) Received: from localhost.localdomain (ec2-13-113-80-70.ap-northeast-1.compute.amazonaws.com. [13.113.80.70]) by smtp.gmail.com with ESMTPSA id s1-20020a17090a2f0100b001f04479017fsm4990927pjd.29.2022.08.06.09.25.37 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 06 Aug 2022 09:25:39 -0700 (PDT) From: Zhang Boyang To: Thomas Gleixner , Ferdinand Blomqvist , linux-kernel@vger.kernel.org Cc: Kees Cook , Randy Dunlap , Zhang Boyang Subject: [PATCH RESEND V3 6/6] rslib: Fix integer overflow on large fcr or prim Date: Sun, 7 Aug 2022 00:25:10 +0800 Message-Id: <20220806162510.157196-7-zhangboyang.id@gmail.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20220806162510.157196-1-zhangboyang.id@gmail.com> References: <20220806162510.157196-1-zhangboyang.id@gmail.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" Current rslib support symsize up to 16, so the max value of rs->nn can be 0xFFFF. Since fcr <=3D nn, prim <=3D nn, multiplications on them can overflow easily, e.g. fcr*root[j], fcr*prim. This patch fixes these problems by introducing rs_modnn_mul(a, b). This function is same as rs_modnn(a*b) but it will avoid overflow when calculating a*b. It requires 0 <=3D a <=3D nn && 0 <=3D b <=3D nn, because = it use uint32_t to do the multiplication internally, so there will be no overflow as long as 0 <=3D a <=3D nn <=3D 0xFFFF && 0 <=3D b <=3D nn <=3D 0= xFFFF. In fact, if we use `unsigned int' everywhere, there is no need to have rs_modnn_mul(). But the `unsigned int' approach has poor scalability and it may bring us to the mess of signed and unsigned integers. With rs_modnn(), the intermediate result is now restricted to [0, nn). This enables us to use rs_modnn_fast(a+b) to replace rs_modnn(a+b), as long as 0 <=3D a+b < 2*nn. The most common case is one addend in [0, nn] and the other addend in [0, nn). The examples of values in [0, nn] are fcr, prim, indexes taken from rs->index_of[0...nn], etc. The examples of values in [0, nn) are results from rs_modnn(), indexes taken from rs->index_of[1...nn], etc. Since the roots of RS generator polynomial, i.e. (fcr+i)*prim%nn, is often used. It's now precomputed into rs->genroot[], to avoid writing rs_modnn_mul(rs, rs_modnn_fast(rs, fcr + i), prim) everywhere. The algorithm of searching for rs->iprim is also changed. Instead of searching for (1+what*nn)%prim =3D=3D 0, then iprim =3D (1+what*nn)/prim, it now searches for iprim*prim%nn =3D=3D 1 directly. A new test case is also added to test_rslib.c to ensure correctness. Signed-off-by: Zhang Boyang --- include/linux/rslib.h | 23 +++++++++++++ lib/reed_solomon/decode_rs.c | 60 +++++++++++++++++++-------------- lib/reed_solomon/reed_solomon.c | 30 ++++++++++++----- lib/reed_solomon/test_rslib.c | 8 ++--- 4 files changed, 83 insertions(+), 38 deletions(-) diff --git a/include/linux/rslib.h b/include/linux/rslib.h index a277a178157b..a11ea5e8eb14 100644 --- a/include/linux/rslib.h +++ b/include/linux/rslib.h @@ -22,6 +22,7 @@ * @alpha_to: exp() lookup table * @index_of: log() lookup table * @genpoly: Generator polynomial + * @genroot: Roots of generator polynomial, index form * @nroots: Number of generator roots =3D number of parity symbols * @fcr: First consecutive root, index form * @prim: Primitive element, index form @@ -37,6 +38,7 @@ struct rs_codec { uint16_t *alpha_to; uint16_t *index_of; uint16_t *genpoly; + uint16_t *genroot; int nroots; int fcr; int prim; @@ -128,6 +130,27 @@ static inline int rs_modnn(struct rs_codec *rs, int x) return x; } =20 +/** + * rs_modnn_mul() - Modulo replacement for galois field arithmetics + * + * @rs: Pointer to the RS codec + * @a: 0 <=3D a <=3D nn ; a*b is the value to reduce + * @b: 0 <=3D b <=3D nn ; a*b is the value to reduce + * + * Same as rs_modnn(a*b), but avoid integer overflow when calculating a*b +*/ +static inline int rs_modnn_mul(struct rs_codec *rs, int a, int b) +{ + /* nn <=3D 0xFFFF, so (a * b) will not overflow uint32_t */ + uint32_t x =3D (uint32_t)a * (uint32_t)b; + uint32_t nn =3D (uint32_t)rs->nn; + while (x >=3D nn) { + x -=3D nn; + x =3D (x >> rs->mm) + (x & nn); + } + return (int)x; +} + /** * rs_modnn_fast() - Modulo replacement for galois field arithmetics * diff --git a/lib/reed_solomon/decode_rs.c b/lib/reed_solomon/decode_rs.c index 6c1d53d1b702..3387465ab429 100644 --- a/lib/reed_solomon/decode_rs.c +++ b/lib/reed_solomon/decode_rs.c @@ -20,6 +20,7 @@ int iprim =3D rs->iprim; uint16_t *alpha_to =3D rs->alpha_to; uint16_t *index_of =3D rs->index_of; + uint16_t *genroot =3D rs->genroot; uint16_t u, q, tmp, num1, num2, den, discr_r, syn_error; int count =3D 0; int num_corrected; @@ -69,8 +70,8 @@ } else { syn[i] =3D ((((uint16_t) data[j]) ^ invmsk) & msk) ^ - alpha_to[rs_modnn(rs, index_of[syn[i]] + - (fcr + i) * prim)]; + alpha_to[rs_modnn_fast(rs, + index_of[syn[i]] + genroot[i])]; } } } @@ -81,8 +82,8 @@ syn[i] =3D ((uint16_t) par[j]) & msk; } else { syn[i] =3D (((uint16_t) par[j]) & msk) ^ - alpha_to[rs_modnn(rs, index_of[syn[i]] + - (fcr+i)*prim)]; + alpha_to[rs_modnn_fast(rs, + index_of[syn[i]] + genroot[i])]; } } } @@ -108,15 +109,17 @@ =20 if (no_eras > 0) { /* Init lambda to be the erasure locator polynomial */ - lambda[1] =3D alpha_to[rs_modnn(rs, - prim * (nn - 1 - (eras_pos[0] + pad)))]; + lambda[1] =3D alpha_to[rs_modnn_mul(rs, + prim, (nn - 1 - (eras_pos[0] + pad)))]; for (i =3D 1; i < no_eras; i++) { - u =3D rs_modnn(rs, prim * (nn - 1 - (eras_pos[i] + pad))); + u =3D rs_modnn_mul(rs, + prim, (nn - 1 - (eras_pos[i] + pad))); for (j =3D i + 1; j > 0; j--) { tmp =3D index_of[lambda[j - 1]]; if (tmp !=3D nn) { lambda[j] ^=3D - alpha_to[rs_modnn(rs, u + tmp)]; + alpha_to[rs_modnn_fast(rs, + u + tmp)]; } } } @@ -137,9 +140,9 @@ for (i =3D 0; i < r; i++) { if ((lambda[i] !=3D 0) && (s[r - i - 1] !=3D nn)) { discr_r ^=3D - alpha_to[rs_modnn(rs, - index_of[lambda[i]] + - s[r - i - 1])]; + alpha_to[rs_modnn_fast(rs, + index_of[lambda[i]] + + s[r - i - 1])]; } } discr_r =3D index_of[discr_r]; /* Index form */ @@ -153,8 +156,8 @@ for (i =3D 0; i < nroots; i++) { if (b[i] !=3D nn) { t[i + 1] =3D lambda[i + 1] ^ - alpha_to[rs_modnn(rs, discr_r + - b[i])]; + alpha_to[rs_modnn_fast(rs, + discr_r + b[i])]; } else t[i + 1] =3D lambda[i + 1]; } @@ -166,8 +169,9 @@ */ for (i =3D 0; i <=3D nroots; i++) { b[i] =3D (lambda[i] =3D=3D 0) ? nn : - rs_modnn(rs, index_of[lambda[i]] - - discr_r + nn); + rs_modnn_fast(rs, + index_of[lambda[i]] + + nn - discr_r); } } else { /* 2 lines below: B(x) <-- x*B(x) */ @@ -197,11 +201,11 @@ /* Find roots of error+erasure locator polynomial by Chien search */ memcpy(®[1], &lambda[1], nroots * sizeof(reg[0])); count =3D 0; /* Number of roots of lambda(x) */ - for (i =3D 1, k =3D iprim - 1; i <=3D nn; i++, k =3D rs_modnn(rs, k + ipr= im)) { + for (i =3D 1, k =3D iprim-1; i <=3D nn; i++, k =3D rs_modnn_fast(rs, k+ip= rim)) { q =3D alpha_to[0]; /* lambda[0] is always 0 */ for (j =3D deg_lambda; j > 0; j--) { if (reg[j] !=3D nn) { - reg[j] =3D rs_modnn(rs, reg[j] + j); + reg[j] =3D rs_modnn_fast(rs, reg[j] + j); q ^=3D alpha_to[reg[j]]; } } @@ -238,8 +242,8 @@ tmp =3D 0; for (j =3D i; j >=3D 0; j--) { if ((s[i - j] !=3D nn) && (lambda[j] !=3D nn)) - tmp ^=3D - alpha_to[rs_modnn(rs, s[i - j] + lambda[j])]; + tmp ^=3D alpha_to[rs_modnn_fast(rs, + s[i - j] + lambda[j])]; } omega[i] =3D index_of[tmp]; } @@ -254,8 +258,9 @@ num1 =3D 0; for (i =3D deg_omega; i >=3D 0; i--) { if (omega[i] !=3D nn) - num1 ^=3D alpha_to[rs_modnn(rs, omega[i] + - i * root[j])]; + num1 ^=3D alpha_to[rs_modnn_fast(rs, + omega[i] + + rs_modnn_mul(rs, i, root[j]))]; } =20 if (num1 =3D=3D 0) { @@ -264,15 +269,18 @@ continue; } =20 - num2 =3D alpha_to[rs_modnn(rs, root[j] * (fcr - 1) + nn)]; + num2 =3D alpha_to[rs_modnn_fast(rs, + rs_modnn_mul(rs, root[j], fcr) + + nn - root[j])]; den =3D 0; =20 /* lambda[i+1] for i even is the formal derivative * lambda_pr of lambda[i] */ for (i =3D min(deg_lambda, nroots - 1) & ~1; i >=3D 0; i -=3D 2) { if (lambda[i + 1] !=3D nn) { - den ^=3D alpha_to[rs_modnn(rs, lambda[i + 1] + - i * root[j])]; + den ^=3D alpha_to[rs_modnn_fast(rs, + lambda[i + 1] + + rs_modnn_mul(rs, i, root[j]))]; } } =20 @@ -292,8 +300,8 @@ if (b[j] =3D=3D 0) continue; =20 - k =3D (fcr + i) * prim * (nn-loc[j]-1); - tmp ^=3D alpha_to[rs_modnn(rs, index_of[b[j]] + k)]; + k =3D rs_modnn_mul(rs, genroot[i], nn - loc[j] - 1); + tmp ^=3D alpha_to[rs_modnn_fast(rs, index_of[b[j]] + k)]; } =20 if (tmp !=3D alpha_to[s[i]]) diff --git a/lib/reed_solomon/reed_solomon.c b/lib/reed_solomon/reed_solomo= n.c index da46026a60b8..2c86e4dfcbaa 100644 --- a/lib/reed_solomon/reed_solomon.c +++ b/lib/reed_solomon/reed_solomon.c @@ -100,6 +100,10 @@ static struct rs_codec *codec_init(int symsize, int gf= poly, int (*gffunc)(int), if(rs->genpoly =3D=3D NULL) goto err; =20 + rs->genroot =3D kmalloc_array(rs->nroots, sizeof(uint16_t), gfp); + if(rs->genroot =3D=3D NULL) + goto err; + /* Generate Galois field lookup tables */ rs->index_of[0] =3D rs->nn; /* log(zero) =3D -inf */ rs->alpha_to[rs->nn] =3D 0; /* alpha**-inf =3D 0 */ @@ -126,26 +130,34 @@ static struct rs_codec *codec_init(int symsize, int g= fpoly, int (*gffunc)(int), goto err; =20 /* Find prim-th root of 1, used in decoding */ - for(iprim =3D 1; (iprim % prim) !=3D 0; iprim +=3D rs->nn); + for (iprim =3D 1; rs_modnn_mul(rs, iprim, prim) !=3D 1; iprim++); /* prim-th root of 1, index form */ - rs->iprim =3D iprim / prim; + rs->iprim =3D iprim; + + /* Precompute generator polynomial roots */ + root =3D rs_modnn_mul(rs, fcr, prim); + for (i =3D 0; i < nroots; i++) { + rs->genroot[i] =3D root; /* =3D (fcr + i) * prim % nn */ + root =3D rs_modnn_fast(rs, root + prim); + } =20 /* Form RS code generator polynomial from its roots */ rs->genpoly[0] =3D rs->alpha_to[0]; - for (i =3D 0, root =3D fcr * prim; i < nroots; i++, root +=3D prim) { + for (i =3D 0; i < nroots; i++) { + root =3D rs->genroot[i]; rs->genpoly[i + 1] =3D rs->alpha_to[0]; /* Multiply rs->genpoly[] by @**(root + x) */ for (j =3D i; j > 0; j--) { if (rs->genpoly[j] !=3D 0) { - rs->genpoly[j] =3D rs->genpoly[j -1] ^ - rs->alpha_to[rs_modnn(rs, + rs->genpoly[j] =3D rs->genpoly[j - 1] ^ + rs->alpha_to[rs_modnn_fast(rs, rs->index_of[rs->genpoly[j]] + root)]; } else rs->genpoly[j] =3D rs->genpoly[j - 1]; } /* rs->genpoly[0] can never be zero */ rs->genpoly[0] =3D - rs->alpha_to[rs_modnn(rs, + rs->alpha_to[rs_modnn_fast(rs, rs->index_of[rs->genpoly[0]] + root)]; } /* convert rs->genpoly[] to index form for quicker encoding */ @@ -157,6 +169,7 @@ static struct rs_codec *codec_init(int symsize, int gfp= oly, int (*gffunc)(int), return rs; =20 err: + kfree(rs->genroot); kfree(rs->genpoly); kfree(rs->index_of); kfree(rs->alpha_to); @@ -188,6 +201,7 @@ void free_rs(struct rs_control *rs) kfree(cd->alpha_to); kfree(cd->index_of); kfree(cd->genpoly); + kfree(cd->genroot); kfree(cd); } mutex_unlock(&rslistlock); @@ -340,7 +354,7 @@ EXPORT_SYMBOL_GPL(encode_rs8); * @data: data field of a given type * @par: received parity data field * @len: data length - * @s: syndrome data field, must be in index form + * @s: syndrome data field, must be in index form, 0 <=3D index <=3D nn * (if NULL, syndrome is calculated) * @no_eras: number of erasures * @eras_pos: position of erasures, can be NULL @@ -393,7 +407,7 @@ EXPORT_SYMBOL_GPL(encode_rs16); * @data: data field of a given type * @par: received parity data field * @len: data length - * @s: syndrome data field, must be in index form + * @s: syndrome data field, must be in index form, 0 <=3D index <=3D nn * (if NULL, syndrome is calculated) * @no_eras: number of erasures * @eras_pos: position of erasures, can be NULL diff --git a/lib/reed_solomon/test_rslib.c b/lib/reed_solomon/test_rslib.c index d9d1c33aebda..a03c7249f920 100644 --- a/lib/reed_solomon/test_rslib.c +++ b/lib/reed_solomon/test_rslib.c @@ -55,6 +55,7 @@ static struct etab Tab[] =3D { {8, 0x11d, 1, 1, 30, 100 }, {8, 0x187, 112, 11, 32, 100 }, {9, 0x211, 1, 1, 33, 80 }, + {16, 0x1ffed, 65534, 65534, 50, 5 }, {0, 0, 0, 0, 0, 0}, }; =20 @@ -232,9 +233,8 @@ static void compute_syndrome(struct rs_control *rsc, ui= nt16_t *data, struct rs_codec *rs =3D rsc->codec; uint16_t *alpha_to =3D rs->alpha_to; uint16_t *index_of =3D rs->index_of; + uint16_t *genroot =3D rs->genroot; int nroots =3D rs->nroots; - int prim =3D rs->prim; - int fcr =3D rs->fcr; int i, j; =20 /* Calculating syndrome */ @@ -245,8 +245,8 @@ static void compute_syndrome(struct rs_control *rsc, ui= nt16_t *data, syn[i] =3D data[j]; } else { syn[i] =3D data[j] ^ - alpha_to[rs_modnn(rs, index_of[syn[i]] - + (fcr + i) * prim)]; + alpha_to[rs_modnn_fast(rs, + index_of[syn[i]] + genroot[i])]; } } } --=20 2.30.2