From nobody Fri Nov 29 04:49:13 2024 Received: from mail-pg1-f175.google.com (mail-pg1-f175.google.com [209.85.215.175]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 2068F1A76D8 for ; Tue, 24 Sep 2024 12:32:27 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.215.175 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1727181149; cv=none; b=fPCb+ZSeYaaFTgz9ceNnPKA6NMNy8vWeOt/DF9RiLbPynd/gA1UVzWXevNOuKWGbO02YLnNHWOgejd7ukPf1pIS3r1oA1n3ozEW3Ll5r3fKmgxpyPUSqGbCqhlf7r0B1Q7+sdAyIbMtJxBM5rnsXo/6cebogb8xgDM9EiIix9Gg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1727181149; c=relaxed/simple; bh=zSEaBEiz0fDT3KRybsgEQnZ7x7PikIZPSwGuq4v+J3U=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=TuO78k6AS8y+XR8YvQGrSxpuHYxs8Xzc4YZ05QXKjnLysBLzMTFJOFxjMOA6JpiQ/zHgCmEwveo5pHVRYjDtqLvrFke0WaS2BVtSb3gpQ1CyAOo853sRc7LeHqa2bJpQNi3izzyVez0e9zdbf2hJ1ALODNnc3ZVHEvIMoKedAUY= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=iWm+oua/; arc=none smtp.client-ip=209.85.215.175 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="iWm+oua/" Received: by mail-pg1-f175.google.com with SMTP id 41be03b00d2f7-7d666fb3fb9so2646578a12.0 for ; Tue, 24 Sep 2024 05:32:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1727181147; x=1727785947; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=/Gpe5z9CsTim9CBbaab66JvpHBddFQKLsRD0FtJ3vuQ=; b=iWm+oua/rC8Vh1R6DOmVOMFckSRvKtJYlN4OersDA6UsarffuICaRjFk1QtLjYSkxm oELSoeyoQ48v7LMWzEym1Y2HRhtGn82A++yJf+k7R/kyDXRAximGTvb5CA0Gd6+k1MYN OqfdbpbmLIArDPrSAq09cMEtg0vQgICyBwo5RRJzfY9QiepZoU8CnFgo2rG0X8uUNbii NnGbibeSqta6dlalWJjCbmuEuwT5BRdxzk/G/C5AFSdHpKNIAkgIM2dXr2YE39D7ZTzc 8k8r5gveaEg1QH+e8Ae1YVdlqSLeYz/zdptH9Ap0wNjAolvfu9uaXuHRMS1n/8awK7++ kU3A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1727181147; x=1727785947; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=/Gpe5z9CsTim9CBbaab66JvpHBddFQKLsRD0FtJ3vuQ=; b=FhjdWUpIUjNwu5PxFNBPeoEpIlQdoS/yBYO/Gf0I8zUAHedCGZYRCl/eLMBMxjWCng XCv0zKFZ5HAfzHK6E3F5Mbi4x4VkI0ZVjIMwCJ4i+rSCgpJCxQfgpUa+yeKXHhDViqnm V0xkSWsW+52W4C04vXg9R8AlzaL+4OlugnI12v9H4vWUXFUlys21+9jcf6scwpFvRhr9 iaQAzFlpvL8VO33/sV4DVorTmMEgFYgS0fyrOdJr2KWCxUZxX4EjhbYCDXvMibkdV+Gh oqslNqDeCdb2WMRy94bN4dAINnBE249xbUkJs+KbzrFZNKUd5K32DF90cWnF1BGL36sw MHMg== X-Forwarded-Encrypted: i=1; AJvYcCWuolieSVD9WaFYHUQGNeHuBC8KwP1aLMBEoYn1Cp6DbqhKs19P0rX5tUdiJyC5JX8qYFz7plmoCT7yW8o=@vger.kernel.org X-Gm-Message-State: AOJu0YySqCjReQJQXrGVQmezHG23gs3ASPRxjpstrL+Os9FAN+ZGolrK XxbqtzlJ4/bMl8JMgZKP8vXqMsZyR5C48ZlH4v35+n54IANqNP5R4YUMOGnI X-Google-Smtp-Source: AGHT+IE1daw3BjAOW6AcSIHY1AWEajlz/uHZbI/qA8szYL3+6yJxj31Lnankac1edCz/KQKQolAgqg== X-Received: by 2002:a05:6a20:e188:b0:1cc:d9dc:5637 with SMTP id adf61e73a8af0-1d343df87f1mr4609820637.23.1727181147175; Tue, 24 Sep 2024 05:32:27 -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 d2e1a72fcca58-71afc9c5ad4sm1115566b3a.188.2024.09.24.05.32.23 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 24 Sep 2024 05:32:26 -0700 (PDT) From: Zhang Boyang To: Linus Torvalds , linux-kernel@vger.kernel.org Cc: Thomas Gleixner , Ferdinand Blomqvist , Kees Cook , Randy Dunlap , Zhang Boyang Subject: [PATCH 1/5] rslib: Fix incorrect documentation of rs_modnn() Date: Tue, 24 Sep 2024 20:31:37 +0800 Message-Id: <20240924123141.16962-2-zhangboyang.id@gmail.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20240924123141.16962-1-zhangboyang.id@gmail.com> References: <20240924123141.16962-1-zhangboyang.id@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable 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). This patch also fixes the kernel-doc style of rs_modnn(). Signed-off-by: Zhang Boyang --- include/linux/rslib.h | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/include/linux/rslib.h b/include/linux/rslib.h index a04dacbdc8ae..f76e0fc097a4 100644 --- a/include/linux/rslib.h +++ b/include/linux/rslib.h @@ -106,7 +106,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 @@ -115,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 Fri Nov 29 04:49:13 2024 Received: from mail-pf1-f177.google.com (mail-pf1-f177.google.com [209.85.210.177]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 764751A7AD2 for ; Tue, 24 Sep 2024 12:32:32 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.177 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1727181153; cv=none; b=bTVDznt7NOrDzxnFnj3gichg6hZaUhClD3SHYyfnv1A83rbHsD5K/FhlmOGdznZma3t9EjiqIqXadFOmFNLy0BBWl9V605x1DjoEI3o/zeZVQdlBxVW9Si16QP+eM9Fkib8uqUt41Qp31MxackDxVqkKf93PfVK1nZyAWoZf7hM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1727181153; c=relaxed/simple; bh=vYyfq1fdnVJNKDHZZ4jwWfoOzvf/EQdKHUP/P8grO/Q=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=EZHGioRFpEL3Vm6O1QA2aXRi0TgCqt7YnvccDCg8UQTG8gMssy5lshKjKd8x5j2kWmOPnViA74tN+mAVWocZHOeXMxDKr1o29nJZF6asD2j8dyXmd87rdKH+Dcq7vxI4KzoXMlwYmlKgGD79WMA693uGQZDy7agh8VZ2+MnMTdQ= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=lSR5kmOW; arc=none smtp.client-ip=209.85.210.177 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="lSR5kmOW" Received: by mail-pf1-f177.google.com with SMTP id d2e1a72fcca58-7178df70f28so4202057b3a.2 for ; Tue, 24 Sep 2024 05:32:32 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1727181152; x=1727785952; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=vFN6t0TJFQnxmv12ewrvdOXYHRD1/G/lf2Fnmv9SgI0=; b=lSR5kmOWj5y8tZSVzsZvInkwCtDs1h7uIKgdvvnut+rMS1vY6KolyiWJOYDeieTZqP SXtOKGiIFwAyxSMqzOh1kkc8Nljexp+Dfdikoz3sU6rWm8rsWYiGHz6xXD0xtu4EnCjj mLvePWSh8xhyYveps07wzFHLgOfxaXJok3JxLBd+AEWwFo2mLNBOMRnpZvahmpdXhl4P sk81W/M8Ki05vvvzOT9A6g/p/Cs1BVNXG/cMp1loQyboBszFf3c1mThD/opqciv/4X0p N82tt1cpOnZ7ZoGdyvBEPQrJ/ZfQKmY0m/DrBHLiz+TqrDkOshWQuoUb3yTTSMDQ9Abb Qc2g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1727181152; x=1727785952; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=vFN6t0TJFQnxmv12ewrvdOXYHRD1/G/lf2Fnmv9SgI0=; b=tqFNECjVIok8d1PRu1/WW/CNxXBPFbvod9oTGCQmPn8F/Hwef1tUYrAk7+Fmos97dU kzj7IPh9ZZYlVW+lr08FN42m07REflB3ejCKlfMuAQ9cU6/KBwYtSUU920Po74Ym+OKu nClqLKXZdbxjf8kthfWuk1bFnXqUXzWB/YaA0hBaZSfxLzAvex9ooNSjpB8xXGmb79i2 e3ErYXPQkHbPY3Ek5tb1e78m1c65F24+iOj3J2WSBVFedugONMkLD3criJ8tWcitH2pO OpRcgkk+YtSDRtriyAPtpaz7JiWA+seAnsy1sYRdcwwbXYmhRlfOs/wItl/PBpHuHnwM 67TQ== X-Forwarded-Encrypted: i=1; AJvYcCUXkJz+yV9ykn/YbQtZ4eB55koWubIjduj0GHzOwU73YkKTKQoiT6jz6+SfpObnAoNEESYT/wUaaFTqUnc=@vger.kernel.org X-Gm-Message-State: AOJu0YwbDzovO+f723VcmoNFucyBtaSYfvxiIfilmAj6Hys7BSPVYQH8 ArIqAxX53EXPSrNG0G6NABiJT/LdBpyemzO5xA1xu0+ivFry4dQt X-Google-Smtp-Source: AGHT+IGIBC+s8z8I1M2LAb5TgNJi8KhjIZjaw41vOl29r8HnH762QSoVson27WbTULXb/X8c1gTiEQ== X-Received: by 2002:a05:6a21:670d:b0:1cc:e409:7d0c with SMTP id adf61e73a8af0-1d30a983b2dmr22206674637.25.1727181151608; Tue, 24 Sep 2024 05:32: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 d2e1a72fcca58-71afc9c5ad4sm1115566b3a.188.2024.09.24.05.32.27 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 24 Sep 2024 05:32:30 -0700 (PDT) From: Zhang Boyang To: Linus Torvalds , linux-kernel@vger.kernel.org Cc: Thomas Gleixner , Ferdinand Blomqvist , Kees Cook , Randy Dunlap , Zhang Boyang Subject: [PATCH 2/5] rslib: Fix documentation of alpha_to[] and index_of[] Date: Tue, 24 Sep 2024 20:31:38 +0800 Message-Id: <20240924123141.16962-3-zhangboyang.id@gmail.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20240924123141.16962-1-zhangboyang.id@gmail.com> References: <20240924123141.16962-1-zhangboyang.id@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Obviously, alpha_to[] is antilog table, and index_of[] is logarithm table. Signed-off-by: Zhang Boyang --- include/linux/rslib.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/include/linux/rslib.h b/include/linux/rslib.h index f76e0fc097a4..908bf7d0eb58 100644 --- a/include/linux/rslib.h +++ b/include/linux/rslib.h @@ -18,8 +18,8 @@ * * @mm: Bits per symbol * @nn: Symbols per block (=3D (1<; Tue, 24 Sep 2024 12:32:36 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.173 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1727181158; cv=none; b=Xzj7Q3RGE04OJFhluSB51imxipl1DgRNxT270fH+7GYeGNB/4a+6pltCV3X9VyGaXnp5aCahE6xYpFWSd2bxSKFN4m+gq8bV7Wc5JkpvStKWZ3akRYq/7hR5tYZ/WOmrBd51Ih2bs3c4wuydYLQcxrWp6Vni6BXd8+3w1zYBojw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1727181158; c=relaxed/simple; bh=ihUrjom1CVLpewOUxHxXnQDiC74uuQESPKR49w6+r30=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=bDvk7cCgwjzKi3kOqjWA2BGawzdGF0uCZSzVvjqNQf/VqAFn6X6xsPuh4xzzeuXNciV6V2P+g2yan+Z5yPSEmxnIlJ5SoCa+rArBgMDPleJfabIm5pLLqmN800G9tdRyDm5tK6uFEe0y8qO/3GNRYtHleabh5n1gdPAK5krppos= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=d6lEXzGV; arc=none smtp.client-ip=209.85.210.173 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="d6lEXzGV" Received: by mail-pf1-f173.google.com with SMTP id d2e1a72fcca58-718d606726cso3682806b3a.3 for ; Tue, 24 Sep 2024 05:32:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1727181156; x=1727785956; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=+HTEls9oNKfjurlW/7JQf2pxCuaRhIqDrMhYGPg6XCE=; b=d6lEXzGVhlZODC4c71978IG8+zwWUWaMXRu07J8BQgyYg0Xkw+fbMCC5PJbGdLLZ+W DPNN39Xls/oAtHrFi6J8xj17ySp6o/KgTRcl1qMI9c8AE9eC+6BVLGCPMQ1eK3iElm0p vd8JlPqZB/4NbIUnwCkN7ERN4BOZLxTdbSP0DFODrsMdQt6Hz+ZRK7W7IbVbHwdcNOq1 vz1sB3Fdrpx5l0HZdBK4Ymm34fJaglv9nxSOXTCYSyKteHij1R/K7Y4yBZnuub6IjPh/ Ohy+ntgELZdNoFnn5MHo2ox+sV3LvKay8xDszzCqPNCuCOb0pnTjapm4VMya35ymdMYq Ubzg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1727181156; x=1727785956; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=+HTEls9oNKfjurlW/7JQf2pxCuaRhIqDrMhYGPg6XCE=; b=ZNudnmkgOglcXCke+dczU4hpyfo1IqjqVrbsqjS2LWUOeS3o0iRlbJGA2LElwVj6+T qNHh3vLvDETSSWmPFb/TYbTPBi2bE9kRVCdgBh7zPksiaTiRt9CXxQlSTaP55CpOTyp+ FqIbS9WSGt8cTudzEoWkbDmMjBUoZE9Vs8dXSmEv8YMtIi1bBJweO7TJ+ro7RKi7xvS6 eOijLRZpRxkq0xI9meaK5XZhZk8eHAuhzjtKMvDI+XoNOs6mJRMCJ6+FjB7PsVg1OmTk z4O7X0AlujKhwOlAT/+gtb1D1oF7Ok618kIrat+Dc030nPEEqrQaVJvKM6+5T+xqoWQG S0bg== X-Forwarded-Encrypted: i=1; AJvYcCUzvTvC+2kCgXNopxV2y06OE+FI011nA2Q+QskPlAjJFvPZlE7dH0A6eNi4KOVyC4t1+5GYARUu9VkOo+4=@vger.kernel.org X-Gm-Message-State: AOJu0YwN2L3v1z4sPvtLgCdzoAMJHanl3UerUBwUc5WnfAbGnR/h1xCs 0qxQw9zIe/AMq8Nkr+ihaLYNY4rdvDMXTVKfGbjOa69Th1Vowp73 X-Google-Smtp-Source: AGHT+IGDCkwZpNocsyz0AWFpALmNxVSU6O0yLt8LNXOO4zrtUvGJA4rbuajl7pvGROR/U99U4Oaixg== X-Received: by 2002:a05:6a20:4388:b0:1d2:e78a:36a2 with SMTP id adf61e73a8af0-1d30c9891d1mr21687125637.8.1727181155920; Tue, 24 Sep 2024 05:32:35 -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 d2e1a72fcca58-71afc9c5ad4sm1115566b3a.188.2024.09.24.05.32.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 24 Sep 2024 05:32:35 -0700 (PDT) From: Zhang Boyang To: Linus Torvalds , linux-kernel@vger.kernel.org Cc: Thomas Gleixner , Ferdinand Blomqvist , Kees Cook , Randy Dunlap , Zhang Boyang Subject: [PATCH 3/5] rslib: Fix wrong result if gffunc(0) != 1 Date: Tue, 24 Sep 2024 20:31:39 +0800 Message-Id: <20240924123141.16962-4-zhangboyang.id@gmail.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20240924123141.16962-1-zhangboyang.id@gmail.com> References: <20240924123141.16962-1-zhangboyang.id@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" 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, leading to errors if gffunc(0) !=3D 1. This patch replaces hard-coded 1 with alpha_to[0] to fix this 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. Fixes: d7e5a5462f68 ("[RSLIB] Support non-canonical GF representations") 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 Fri Nov 29 04:49:13 2024 Received: from mail-pf1-f176.google.com (mail-pf1-f176.google.com [209.85.210.176]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 373192907 for ; Tue, 24 Sep 2024 12:32:40 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.176 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1727181163; cv=none; b=q7LIEzNUnzDyJOpo8vnv0Bex3nEtFL9bv54aaF0fGZwWLSJb80/k8RdGSf4cjhZvMACJLtMEPIJ5v/Ejx8pm8UCjUURtnJGmuyKJ9N9bU8boingXU0WwTg35ButFr8psVS0ZvkncerNc/8KLJXJepHaQLzpTY8FztJwdsmyWjI0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1727181163; c=relaxed/simple; bh=p+SlC9+iWsoYOkzR6USkIX63Q4voGnHbuqMuTP5Qk6A=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=Y7qISKNWFPAIZUpcuiI/vTdjjm0mcNAMZp1TzpaOpAtk9uLq99CWRNemcYcNLEUJzGNY2jrGwc0OfIhGk242Jrn3Q5+LpOXlmAIuTDibrmfCuPmyFNZ//6sZ7uCegRfHLP0uXDekybUqYsMx5kcXR1Gj/9CUamMQfXDlRY6OW6Q= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=jg5xyrGB; arc=none smtp.client-ip=209.85.210.176 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="jg5xyrGB" Received: by mail-pf1-f176.google.com with SMTP id d2e1a72fcca58-71b070ff24dso114194b3a.2 for ; Tue, 24 Sep 2024 05:32:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1727181160; x=1727785960; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=g2CQ3g+a9Pxs3bYyycBG+VPiOxu/RQcJ2VdogNTviFY=; b=jg5xyrGBHT3DIGyvTvleYW6tz1THZZhtdnYFyuzpLIIwwKpsnDoPt65QYG6a618E7E jU8trfJAIV7hMbomUUM0KemDQ/Y55UL0X8kB56wt/52di7RTkhSh77Oc3e9rFe00gXhF xn+OdcKO6LzUZxx1PsIR8kRBvcK1HxklLsKPXYQXWDpV0TY/sT208qFP6EOOR6x9VZfS LnfWVe1sbkQM7F0KEoc323i15cBJgLJ7SM0a0QKuXM+IsL81S0kUJuY3QWuRJzcgfOiv n6VkdTim4h+9Qfy+IVAnFyGkZF0+JnKd8rURF4B2Ew2rI9dofdWhBDZskTIDaAFUPjQ3 xRpg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1727181160; x=1727785960; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=g2CQ3g+a9Pxs3bYyycBG+VPiOxu/RQcJ2VdogNTviFY=; b=ug+0UaAPRn3Or3WDfi2vY5zPF5VnO4b9QcgN85W8uc8ywrpz/PTAIhc8RuZhP23aru 5rF6CAy8GZ+9pj7WUc1X2nk4b5prw7dyUj6YcIRWM039ILCOaekw0Q6lPmCpjMH1R0ld 1E/4/HfmegS4oXPPoBmwRBWiSDgLdTsufK2sOCFuGnu6Mu22rmpY4OKb/LAEX7K8qY1Q O1BZZz5a8drWC93jzfN2uW5Ipq+MF3CXuNlAiD89Gs2wawz+TlG0h4KAjeYMV4PVAfrC if2Dj8kM3XzQzY+shT89eAyG/Y2zK9nuM7MdCLFhqWG8Z+THB8/lI1d5S4CU+1n5UWO7 UbqQ== X-Forwarded-Encrypted: i=1; AJvYcCUz74V+D4der33227g8unthYI7bP3fQ1JtCybJoveHZg7FUhGIenp7bTQGyWlkYEc08JqliJSVbAuTH1LU=@vger.kernel.org X-Gm-Message-State: AOJu0Yxsfx5720xg/o0llcJD/i6cWo2DVcv0cQMdt2JPqOt7RLK4ujHi GO2eBjsW9ZF9ZFeewhA819AforHnDOM3uExDW+FlAn/8QCQJV0pS X-Google-Smtp-Source: AGHT+IEmU39wcdMD7Hu+761mCwaWe1nxzhCQtivLc6GjEntFU8SDmx+NYyq927LMPvKJT+boqhoojg== X-Received: by 2002:a05:6a00:4650:b0:717:8d81:e548 with SMTP id d2e1a72fcca58-7199c939056mr22079935b3a.1.1727181160349; Tue, 24 Sep 2024 05:32:40 -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 d2e1a72fcca58-71afc9c5ad4sm1115566b3a.188.2024.09.24.05.32.36 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 24 Sep 2024 05:32:39 -0700 (PDT) From: Zhang Boyang To: Linus Torvalds , linux-kernel@vger.kernel.org Cc: Thomas Gleixner , Ferdinand Blomqvist , Kees Cook , Randy Dunlap , Zhang Boyang Subject: [PATCH 4/5] rslib: Improve the performance of encode_rs.c Date: Tue, 24 Sep 2024 20:31:40 +0800 Message-Id: <20240924123141.16962-5-zhangboyang.id@gmail.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20240924123141.16962-1-zhangboyang.id@gmail.com> References: <20240924123141.16962-1-zhangboyang.id@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable 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 908bf7d0eb58..d228ece01069 100644 --- a/include/linux/rslib.h +++ b/include/linux/rslib.h @@ -110,7 +110,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: the value to reduce (requires x >=3D 0) * * where * rs->mm =3D number of bits per symbol @@ -127,4 +127,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: the value to reduce (requires 0 <=3D x < 2*nn) + * + * 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 Fri Nov 29 04:49:13 2024 Received: from mail-pf1-f182.google.com (mail-pf1-f182.google.com [209.85.210.182]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id A29ED1A704B for ; Tue, 24 Sep 2024 12:32:46 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.182 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1727181168; cv=none; b=leQJ5+UuAjMTjqBShSauSnFsRfPQyb6PPOReGHTwigbgx2cLHjU3FmkduIHFNp/bknh42X8for8QwUoDOZxwmyw5zpc1Gw7CTnet4LzOpsHsknO9gOMx3C2wtDVqP5sdUrHxcefzBxVliu7AYJXBDYVMUeb3o6Al0w/Np1Gb/TQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1727181168; c=relaxed/simple; bh=QNKItu6CdIakAOu8t/P7mCLBm64PWWxflE4fgw4oi3g=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=cNCHkcv2mU7wMz2+rEZr9jrBh6ptnXczCezSFa0HtslhrKff4+c/SYJEqfF/qCxXkCwpprX9lw4XmiYBbBVQoulnB44VavXl958ue00Hp+C5bVi/zV5CGvExDI3Y6zBsHWqYbzmv7EUp05LHOz/ES7G7cjcfjl1t2KevZGab5Pk= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=e/a/X+6K; arc=none smtp.client-ip=209.85.210.182 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="e/a/X+6K" Received: by mail-pf1-f182.google.com with SMTP id d2e1a72fcca58-719ba0654f9so1847868b3a.3 for ; Tue, 24 Sep 2024 05:32:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1727181166; x=1727785966; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=/EBQ39GffQsZFZpD0Yw16lUj/HxiDKUxWG4rj+AWg4M=; b=e/a/X+6KflmeZM8pMKVqvjPCYM8boze5n+DB4UVhUvWi9IKb285DN2zuskzNtUtVcJ 4AT7WhBNhGuO72UnJ90pzq0NG+Df4Khn76swojhZSBT5qL9AtRq6xaxP2Tbl+UQEZ+2n Sv2wqWoj601S+ac335ZZACMGzCi4EzUhK9Ku3I9Od3U3oUsAqBDCaVOZZIRLIOqNdNfQ u0ybpdAMs8NuFpuHe1/8s8mNIjUZEW45LSbzK8Bxd6kuXM5Q1Gv825EFgtAaGfQN1kCE U1Ufdv3nKK7AMrRiJs+AlBhJNDQ/O+0m87jSFtgUQL0j2H0OYv5iAOnvF75Y35dG+2aT aqaQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1727181166; x=1727785966; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=/EBQ39GffQsZFZpD0Yw16lUj/HxiDKUxWG4rj+AWg4M=; b=OW+R0puVe0eKvxw4kfa84Ztwz/MtRwsf6PfgVMsZszcDKkDWkB8+AgR98H5kzKNWLE Ons7f4BGVzxD/MxqfGcfRVdKiUt9P+zlvERAgZj02xtgAuy3FmAiHsBI153sAWgnnBMh t4heJqmrmqazJYEJdgAYuiQZDM70NIbMf1M4fZaCTMXN6G/RzmqakFCBG3xxf+099SKI sn1uU7k53NngTi2hJl77h4OL/Jz4E+2mDFuBYEaBZpwPhhwXVvkY7gTpZerqSh7OQOAx unWk5ekIDg1MAgw4TzlWfiT0jA77QAsaaiQpgIJviZXEwzrtJT7lFRWbEeRmfudM4YPx aNzg== X-Forwarded-Encrypted: i=1; AJvYcCV1I1Py4P6tpEEydsmjsuwsx1QL99fRZ2y8yxRNqi7EUTBNHab3Rw1fWhIsPEneDQI8hl2N6UTU1NlyyEY=@vger.kernel.org X-Gm-Message-State: AOJu0Yxz3sfLkccx811oTzJz5kcIKJpw8pYyFvrqZHC7vLy3cecx4VzG Wyu+EmraKjEtlc0jwhv9HgC5WP63Arl29r72DyEJCVG6K/GVkx35TdMBsuZQ X-Google-Smtp-Source: AGHT+IGCSqf1DBXQ7C8vsjx2/P5PZ6pstXz6iz89pk6/TkaeZX/BxgiAbUeFbe/aJaiNKsjLhXVksg== X-Received: by 2002:a05:6a20:cf8f:b0:1cf:2513:89f9 with SMTP id adf61e73a8af0-1d30aa0c5aemr17606608637.39.1727181165709; Tue, 24 Sep 2024 05:32:45 -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 d2e1a72fcca58-71afc9c5ad4sm1115566b3a.188.2024.09.24.05.32.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 24 Sep 2024 05:32:44 -0700 (PDT) From: Zhang Boyang To: Linus Torvalds , linux-kernel@vger.kernel.org Cc: Thomas Gleixner , Ferdinand Blomqvist , Kees Cook , Randy Dunlap , Zhang Boyang Subject: [PATCH 5/5] rslib: Fix 16-bit symbol support Date: Tue, 24 Sep 2024 20:31:41 +0800 Message-Id: <20240924123141.16962-6-zhangboyang.id@gmail.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20240924123141.16962-1-zhangboyang.id@gmail.com> References: <20240924123141.16962-1-zhangboyang.id@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Current rslib support symsize up to 16, so the max value of rs->nn can be up to 0xFFFF. Since fcr <=3D nn, prim <=3D nn, multiplications on them might overflow and lead to wrong results, e.g. fcr*root[j], fcr*prim. This patch fixes these overflows by introducing rs_modnn_mul(a, b). This function is same as rs_modnn(a*b) but it avoids overflow when calculating a*b. It requires 0 <=3D a <=3D nn && 0 <=3D b <=3D nn. As it use uint32_t to do the multiplication internally, there will be no overflow as long as 0 <=3D a <=3D nn <=3D 0xFFFF && 0 <=3D b <=3D nn <=3D 0xFFFF. In= fact, if we use `unsigned int' everywhere, there is no need to introduce 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 | 28 +++++++++++---- lib/reed_solomon/test_rslib.c | 8 ++--- 4 files changed, 82 insertions(+), 37 deletions(-) diff --git a/include/linux/rslib.h b/include/linux/rslib.h index d228ece01069..4fb27d5bdb55 100644 --- a/include/linux/rslib.h +++ b/include/linux/rslib.h @@ -21,6 +21,7 @@ * @alpha_to: Antilog 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 @@ -36,6 +37,7 @@ struct rs_codec { uint16_t *alpha_to; uint16_t *index_of; uint16_t *genpoly; + uint16_t *genroot; int nroots; int fcr; int prim; @@ -127,6 +129,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: a*b is the value to reduce (requires 0 <=3D a <=3D nn <=3D 0xFFFF) + * @b: a*b is the value to reduce (requires 0 <=3D b <=3D nn <=3D 0xFFFF) + * + * 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 bb4f44c8edba..b924eeb98685 100644 --- a/lib/reed_solomon/reed_solomon.c +++ b/lib/reed_solomon/reed_solomon.c @@ -56,7 +56,7 @@ static DEFINE_MUTEX(rslistlock); =20 /** * codec_init - Initialize a Reed-Solomon codec - * @symsize: symbol size, bits (1-8) + * @symsize: symbol size, bits (1-16) * @gfpoly: Field generator polynomial coefficients * @gffunc: Field generator function * @fcr: first root of RS code generator polynomial, index form @@ -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); diff --git a/lib/reed_solomon/test_rslib.c b/lib/reed_solomon/test_rslib.c index 75cb1adac884..d19c95bcd31d 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