Feedback-ID: ic6394509:Fastmail
User-Agent: Cyrus-JMAP/3.11.0-alpha0-566-g3812ddbbc-fm-20240627.001-g3812ddbb
MIME-Version: 1.0
Message-Id: <33c51978-8ee8-438c-9804-e46c0ca8f3f9@app.fastmail.com>
In-Reply-To: <27d42b25-f328-4231-9db0-3811dc77c8cf@app.fastmail.com>
References: <44d2ffca-d560-4919-b85a-4d07060946aa@app.fastmail.com>
 <87zfr1e1uj.fsf@wibble.ilmari.org>
 <9ff90ff9-5ac1-4529-b2f4-f93b37734b9c@app.fastmail.com>
 <81348268-b9fd-4308-bf52-056070aa7c2a@app.fastmail.com>
 <f25ddfc8-4f02-4e8f-8e74-0532f48d0817@app.fastmail.com>
 <CAEZATCV2qPTGo2Fd8xDs06Q7iU5aorgSa9+Fw9zkuQv1y15rcw@mail.gmail.com>
 <8e909218-1965-4515-99e3-4bb5b625e004@app.fastmail.com>
 <CAEZATCWEou=NjpvS-r1WxymbAYihsdKQoQBj1HfBeocoNcv5Ww@mail.gmail.com>
 <bbc62c2d-1173-4454-9e17-be99437c0e7e@app.fastmail.com>
 <0459ded5-6daf-4bf0-9ab0-e1f11ab15ec6@app.fastmail.com>
 <CAEZATCW+N9qaE=5_1xcB0isMrirojN=Bd0yY4Pw67iji4swYiQ@mail.gmail.com>
 <4e54bf4f-59fe-4c9a-b446-a2b64cbfd584@app.fastmail.com>
 <fb6e4aa6-54e1-4be4-a7f6-3edc99aa7e6e@app.fastmail.com>
 <27d42b25-f328-4231-9db0-3811dc77c8cf@app.fastmail.com>
Date: Tue, 02 Jul 2024 22:10:27 +0200
From: "Joel Jacobson" <joel@compiler.org>
To: "Dean Rasheed" <dean.a.rasheed@gmail.com>
Cc: =?UTF-8?Q?Dagfinn_Ilmari_Manns=C3=A5ker?= <ilmari@ilmari.org>,
 pgsql-hackers <pgsql-hackers@postgresql.org>
Subject: Re: Optimize numeric multiplication for one and two base-NBASE digit
 multiplicands.
Content-Type: multipart/mixed;
 boundary=2fdc1d34ec6245279a4d1deaf63faa68
Archived-At: <https://www.postgresql.org/message-id/33c51978-8ee8-438c-9804-e46c0ca8f3f9%40app.fastmail.com>
Precedence: bulk

--2fdc1d34ec6245279a4d1deaf63faa68
Content-Type: text/plain

On Tue, Jul 2, 2024, at 21:55, Joel Jacobson wrote:
> On Tue, Jul 2, 2024, at 20:53, Joel Jacobson wrote:
>> Trying to wrap my head around what could cause this.

I found the bug in the case 3 code,
and it turns out the same type of bug also exists in the case 2 code:

			case 2:
				newdig = (int) var1digits[1] * var2digits[res_ndigits - 4];

The problem here is that res_ndigits could become less than 4,
if rscale is low enough,
and then we would try to access a negative array index in var2digits.

Fix:

			case 2:
				if (res_ndigits - 4 >= 0 && res_ndigits - 4 < var2ndigits)
					newdig = (int) var1digits[1] * var2digits[res_ndigits - 4];
				else
					newdig = 0;

Another problem in the case 2 code:

				if (res_ndigits - 3 < var2ndigits)
					newdig += (int) var1digits[0] * var2digits[res_ndigits - 3];

Fix:

				if (res_ndigits - 3 >= 0 && res_ndigits - 3 < var2ndigits)
					newdig += (int) var1digits[0] * var2digits[res_ndigits - 3];

New version attached that fixes both the case 2 and case 3 code.

Regards,
Joel
--2fdc1d34ec6245279a4d1deaf63faa68
Content-Disposition: attachment;
	filename*0="v4-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch"
Content-Type: application/octet-stream;
	name="=?UTF-8?Q?v4-optimize-numeric-mul=5Fvar-small-var1-arbitrary-var2.patch?="
Content-Transfer-Encoding: BASE64

RnJvbSBhN2Q0MjFkNWZjZDRmNmIzNjdmMjY2YzNiMDA1YzgyYWJmZjAzZDdjIE1vbiBTZXAg
MTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBKb2VsIEpha29ic3NvbiA8Z2l0aHViQGNvbXBpbGVy
Lm9yZz4KRGF0ZTogVHVlLCAyIEp1bCAyMDI0IDE3OjU0OjI1ICswMjAwClN1YmplY3Q6IFtQ
QVRDSF0gbnVtZXJpYzogU2ltcGxpZmllZCBmYXN0LXBhdGggY29tcHV0YXRpb24gZm9yIG11
bF92YXIoKQoKLS0tCiBzcmMvYmFja2VuZC91dGlscy9hZHQvbnVtZXJpYy5jIHwgMTA2ICsr
KysrKysrKysrKysrKysrKysrKysrKysrKysrKysrCiAxIGZpbGUgY2hhbmdlZCwgMTA2IGlu
c2VydGlvbnMoKykKCmRpZmYgLS1naXQgYS9zcmMvYmFja2VuZC91dGlscy9hZHQvbnVtZXJp
Yy5jIGIvc3JjL2JhY2tlbmQvdXRpbHMvYWR0L251bWVyaWMuYwppbmRleCA1NTEwYTIwM2Iw
Li5lM2JjMjliNjI2IDEwMDY0NAotLS0gYS9zcmMvYmFja2VuZC91dGlscy9hZHQvbnVtZXJp
Yy5jCisrKyBiL3NyYy9iYWNrZW5kL3V0aWxzL2FkdC9udW1lcmljLmMKQEAgLTg3NDcsNiAr
ODc0NywxMTIgQEAgbXVsX3Zhcihjb25zdCBOdW1lcmljVmFyICp2YXIxLCBjb25zdCBOdW1l
cmljVmFyICp2YXIyLCBOdW1lcmljVmFyICpyZXN1bHQsCiAJCXJldHVybjsKIAl9CiAKKwkv
KgorCSAqIFNpbXBsaWZpZWQgZmFzdC1wYXRoIGNvbXB1dGF0aW9uLCBpZiB2YXIxIGhhcyBq
dXN0IG9uZSBvciB0d28gZGlnaXRzLgorCSAqIFRoaXMgaXMgc2lnbmlmaWNhbnRseSBmYXN0
ZXIsIHNpbmNlIGl0IGF2b2lkcyBhbGxvY2F0aW5nIGEgc2VwYXJhdGUKKwkgKiBkaWdpdCBh
cnJheSwgbWFraW5nIG11bHRpcGxlIHBhc3NlcyBvdmVyIHZhcjIsIGFuZCBoYXZpbmcgc2Vw
YXJhdGUKKwkgKiBjYXJyeS1wcm9wYWdhdGlvbiBwYXNzZXMuCisJICovCisJaWYgKHZhcjFu
ZGlnaXRzIDw9IDMpCisJeworCQlOdW1lcmljRGlnaXQgKnJlc19idWY7CisKKwkJLyogQWxs
b2NhdGUgcmVzdWx0IGRpZ2l0IGFycmF5ICovCisJCXJlc19idWYgPSBkaWdpdGJ1Zl9hbGxv
YyhyZXNfbmRpZ2l0cyk7CisJCXJlc19idWZbMF0gPSAwOwkJCQkvKiBzcGFyZSBkaWdpdCBm
b3IgbGF0ZXIgcm91bmRpbmcgKi8KKwkJcmVzX2RpZ2l0cyA9IHJlc19idWYgKyAxOworCisJ
CS8qCisJCSAqIENvbXB1dGUgdGhlIHJlc3VsdCBkaWdpdHMgZGlyZWN0bHksIGluIG9uZSBw
YXNzLCBwcm9wYWdhdGluZyB0aGUKKwkJICogY2FycnkgdXAgYXMgd2UgZ28uCisJCSAqLwor
CQlzd2l0Y2ggKHZhcjFuZGlnaXRzKQorCQl7CisJCQljYXNlIDE6CisJCQkJY2FycnkgPSAw
OworCQkJCWZvciAoaSA9IHJlc19uZGlnaXRzIC0gMzsgaSA+PSAwOyBpLS0pCisJCQkJewor
CQkJCQluZXdkaWcgPSAoaW50KSB2YXIxZGlnaXRzWzBdICogdmFyMmRpZ2l0c1tpXSArIGNh
cnJ5OworCQkJCQlyZXNfZGlnaXRzW2kgKyAxXSA9IChOdW1lcmljRGlnaXQpIChuZXdkaWcg
JSBOQkFTRSk7CisJCQkJCWNhcnJ5ID0gbmV3ZGlnIC8gTkJBU0U7CisJCQkJfQorCQkJCXJl
c19kaWdpdHNbMF0gPSAoTnVtZXJpY0RpZ2l0KSBjYXJyeTsKKwkJCQlicmVhazsKKworCQkJ
Y2FzZSAyOgorCQkJCWlmIChyZXNfbmRpZ2l0cyAtIDQgPj0gMCAmJiByZXNfbmRpZ2l0cyAt
IDQgPCB2YXIybmRpZ2l0cykKKwkJCQkJbmV3ZGlnID0gKGludCkgdmFyMWRpZ2l0c1sxXSAq
IHZhcjJkaWdpdHNbcmVzX25kaWdpdHMgLSA0XTsKKwkJCQllbHNlCisJCQkJCW5ld2RpZyA9
IDA7CisJCQkJaWYgKHJlc19uZGlnaXRzIC0gMyA+PSAwICYmIHJlc19uZGlnaXRzIC0gMyA8
IHZhcjJuZGlnaXRzKQorCQkJCQluZXdkaWcgKz0gKGludCkgdmFyMWRpZ2l0c1swXSAqIHZh
cjJkaWdpdHNbcmVzX25kaWdpdHMgLSAzXTsKKwkJCQlyZXNfZGlnaXRzW3Jlc19uZGlnaXRz
IC0gMl0gPSAoTnVtZXJpY0RpZ2l0KSAobmV3ZGlnICUgTkJBU0UpOworCQkJCWNhcnJ5ID0g
bmV3ZGlnIC8gTkJBU0U7CisJCQkJZm9yIChpID0gcmVzX25kaWdpdHMgLSA0OyBpID49IDE7
IGktLSkKKwkJCQl7CisJCQkJCW5ld2RpZyA9IChpbnQpIHZhcjFkaWdpdHNbMF0gKiB2YXIy
ZGlnaXRzW2ldICsKKwkJCQkJCShpbnQpIHZhcjFkaWdpdHNbMV0gKiB2YXIyZGlnaXRzW2kg
LSAxXSArIGNhcnJ5OworCQkJCQlyZXNfZGlnaXRzW2kgKyAxXSA9IChOdW1lcmljRGlnaXQp
IChuZXdkaWcgJSBOQkFTRSk7CisJCQkJCWNhcnJ5ID0gbmV3ZGlnIC8gTkJBU0U7CisJCQkJ
fQorCQkJCW5ld2RpZyA9IChpbnQpIHZhcjFkaWdpdHNbMF0gKiB2YXIyZGlnaXRzWzBdICsg
Y2Fycnk7CisJCQkJcmVzX2RpZ2l0c1sxXSA9IChOdW1lcmljRGlnaXQpIChuZXdkaWcgJSBO
QkFTRSk7CisJCQkJcmVzX2RpZ2l0c1swXSA9IChOdW1lcmljRGlnaXQpIChuZXdkaWcgLyBO
QkFTRSk7CisJCQkJYnJlYWs7CisKKwkJCWNhc2UgMzoKKwkJCQlpZiAocmVzX25kaWdpdHMg
LSA1ID49IDAgJiYgcmVzX25kaWdpdHMgLSA1IDwgdmFyMm5kaWdpdHMpCisJCQkJCW5ld2Rp
ZyA9IChpbnQpIHZhcjFkaWdpdHNbMl0gKiB2YXIyZGlnaXRzW3Jlc19uZGlnaXRzIC0gNV07
CisJCQkJZWxzZQorCQkJCQluZXdkaWcgPSAwOworCQkJCWlmIChyZXNfbmRpZ2l0cyAtIDQg
Pj0gMCAmJiByZXNfbmRpZ2l0cyAtIDQgPCB2YXIybmRpZ2l0cykKKwkJCQkJbmV3ZGlnICs9
IChpbnQpIHZhcjFkaWdpdHNbMV0gKiB2YXIyZGlnaXRzW3Jlc19uZGlnaXRzIC0gNF07CisJ
CQkJaWYgKHJlc19uZGlnaXRzIC0gMyA+PSAwICYmIHJlc19uZGlnaXRzIC0gMyA8IHZhcjJu
ZGlnaXRzKQorCQkJCQluZXdkaWcgKz0gKGludCkgdmFyMWRpZ2l0c1swXSAqIHZhcjJkaWdp
dHNbcmVzX25kaWdpdHMgLSAzXTsKKwkJCQlyZXNfZGlnaXRzW3Jlc19uZGlnaXRzIC0gMl0g
PSAoTnVtZXJpY0RpZ2l0KSAobmV3ZGlnICUgTkJBU0UpOworCQkJCWNhcnJ5ID0gbmV3ZGln
IC8gTkJBU0U7CisJCQkJZm9yIChpID0gcmVzX25kaWdpdHMgLSA0OyBpID49IDI7IGktLSkK
KwkJCQl7CisJCQkJCW5ld2RpZyA9IGNhcnJ5OworCQkJCQlpZiAoaSA8IHZhcjJuZGlnaXRz
KQorCQkJCQkJbmV3ZGlnICs9IChpbnQpIHZhcjFkaWdpdHNbMF0gKiB2YXIyZGlnaXRzW2ld
OworCQkJCQlpZiAoaSAtIDEgPj0gMCAmJiBpIC0gMSA8IHZhcjJuZGlnaXRzKQorCQkJCQkJ
bmV3ZGlnICs9IChpbnQpIHZhcjFkaWdpdHNbMV0gKiB2YXIyZGlnaXRzW2kgLSAxXTsKKwkJ
CQkJaWYgKGkgLSAyID49IDAgJiYgaSAtIDIgPCB2YXIybmRpZ2l0cykKKwkJCQkJCW5ld2Rp
ZyArPSAoaW50KSB2YXIxZGlnaXRzWzJdICogdmFyMmRpZ2l0c1tpIC0gMl07CisJCQkJCXJl
c19kaWdpdHNbaSArIDFdID0gKE51bWVyaWNEaWdpdCkgKG5ld2RpZyAlIE5CQVNFKTsKKwkJ
CQkJY2FycnkgPSBuZXdkaWcgLyBOQkFTRTsKKwkJCQl9CisJCQkJbmV3ZGlnID0gY2Fycnk7
CisJCQkJaWYgKHZhcjJuZGlnaXRzID4gMSkKKwkJCQkJbmV3ZGlnICs9IChpbnQpIHZhcjFk
aWdpdHNbMF0gKiB2YXIyZGlnaXRzWzFdOworCQkJCWlmICh2YXIybmRpZ2l0cyA+IDApCisJ
CQkJCW5ld2RpZyArPSAoaW50KSB2YXIxZGlnaXRzWzFdICogdmFyMmRpZ2l0c1swXTsKKwkJ
CQlyZXNfZGlnaXRzWzJdID0gKE51bWVyaWNEaWdpdCkgKG5ld2RpZyAlIE5CQVNFKTsKKwkJ
CQljYXJyeSA9IG5ld2RpZyAvIE5CQVNFOworCQkJCW5ld2RpZyA9IChpbnQpIHZhcjFkaWdp
dHNbMF0gKiB2YXIyZGlnaXRzWzBdICsgY2Fycnk7CisJCQkJcmVzX2RpZ2l0c1sxXSA9IChO
dW1lcmljRGlnaXQpIChuZXdkaWcgJSBOQkFTRSk7CisJCQkJcmVzX2RpZ2l0c1swXSA9IChO
dW1lcmljRGlnaXQpIChuZXdkaWcgLyBOQkFTRSk7CisJCQkJYnJlYWs7CisJCX0KKworCQkv
KiBTdG9yZSB0aGUgcHJvZHVjdCBpbiByZXN1bHQgKG1pbnVzIGV4dHJhIHJvdW5kaW5nIGRp
Z2l0KSAqLworCQlkaWdpdGJ1Zl9mcmVlKHJlc3VsdC0+YnVmKTsKKwkJcmVzdWx0LT5uZGln
aXRzID0gcmVzX25kaWdpdHMgLSAxOworCQlyZXN1bHQtPmJ1ZiA9IHJlc19idWY7CisJCXJl
c3VsdC0+ZGlnaXRzID0gcmVzX2RpZ2l0czsKKwkJcmVzdWx0LT53ZWlnaHQgPSByZXNfd2Vp
Z2h0IC0gMTsKKwkJcmVzdWx0LT5zaWduID0gcmVzX3NpZ247CisKKwkJLyogUm91bmQgdG8g
dGFyZ2V0IHJzY2FsZSAoYW5kIHNldCByZXN1bHQtPmRzY2FsZSkgKi8KKwkJcm91bmRfdmFy
KHJlc3VsdCwgcnNjYWxlKTsKKworCQkvKiBTdHJpcCBsZWFkaW5nIGFuZCB0cmFpbGluZyB6
ZXJvZXMgKi8KKwkJc3RyaXBfdmFyKHJlc3VsdCk7CisKKwkJcmV0dXJuOworCX0KKwogCS8q
CiAJICogV2UgZG8gdGhlIGFyaXRobWV0aWMgaW4gYW4gYXJyYXkgImRpZ1tdIiBvZiBzaWdu
ZWQgaW50J3MuICBTaW5jZQogCSAqIElOVF9NQVggaXMgbm90aWNlYWJseSBsYXJnZXIgdGhh
biBOQkFTRSpOQkFTRSwgdGhpcyBnaXZlcyB1cyBoZWFkcm9vbQotLSAKMi40NS4xCgo=

--2fdc1d34ec6245279a4d1deaf63faa68--