)]}'
{
  "commit": "89eb6ddbf52887631ca45ad2242862515cd698ab",
  "tree": "136b4da52fe367e0d15f693184d5929f6c0197d2",
  "parents": [
    "48b1f45203f64e2c273736ef2deaef7bb0fa7095"
  ],
  "author": {
    "name": "David Benjamin",
    "email": "davidben@google.com",
    "time": "Fri Mar 14 17:04:07 2025 +0900"
  },
  "committer": {
    "name": "Boringssl LUCI CQ",
    "email": "boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com",
    "time": "Sat Mar 15 09:52:10 2025 -0700"
  },
  "message": "Remove Karatsuba multiplication in BIGNUM\n\nBN_mul, for sufficiently large inputs, uses Karatsuba multiplication\nfrom OpenSSL, but one that we later modified to compute the absolute\nvalue in constant time.\n\nThe value of this complexity has always been odd. BN_mul is not a\nperformance-sensitive operation... except when it is. Almost all of our\nmultiplications are Montgomery modular multiplication. On x86 and Arm,\n32-bit and 64-bit, we have a bn_mul_mont assembly function which\nimplements the two operations combined. But, when bn_mul_mont is not\navailable, we use BN_mul followed by a Montgomery reduction.\n\nAt one point I remember benchmarking this and concluding that, in builds\nwhere it matters (i.e. no-asm), the Karatsuba multiplication was an\nimpactful optimization.\n\nIt would be nice to remove this code. The shape of our BIGNUM\nabstractions means we need to account for operands being differently\nsized, even though our cryptography code actually knows the sizes of\nthings (a sign that we should rethink those abstractions a bit). It also\nmakes reasoning about the scratch spaces of these functions difficult,\nwhich in turn makes it difficult to remove BN_CTX.\n\nThat it\u0027s only useful in no-asm (and niche CPU arches) is probably\nenough to justify removing it. But I\u0027ve benchmarked it again and I\u0027m not\nsure why I thought it was beneficial on even no-asm builds. Running the\nbenchmarks again, it\u0027s either harmful or a hash.\n\nSo, let\u0027s remove it. This CL is just a straightforward deletion of\nunreachable code. We can probably clean this up a bit from here.\n\nApple M1 Pro, OPENSSL_NO_ASM\nBefore:\nDid 1000 RSA 2048 signing operations in 1007150us (992.9 ops/sec)\nDid 45000 RSA 2048 verify (same key) operations in 1004117us (44815.5 ops/sec)\nDid 41000 RSA 2048 verify (fresh key) operations in 1012323us (40500.9 ops/sec)\nDid 10444 RSA 2048 private key parse operations in 1021921us (10220.0 ops/sec)\nDid 416 RSA 3072 signing operations in 1053261us (395.0 ops/sec)\nDid 24000 RSA 3072 verify (same key) operations in 1041675us (23039.8 ops/sec)\nDid 22000 RSA 3072 verify (fresh key) operations in 1038466us (21185.1 ops/sec)\nDid 5604 RSA 3072 private key parse operations in 1056724us (5303.2 ops/sec)\nDid 168 RSA 4096 signing operations in 1018456us (165.0 ops/sec)\nDid 13000 RSA 4096 verify (same key) operations in 1072555us (12120.6 ops/sec)\nDid 12000 RSA 4096 verify (fresh key) operations in 1068795us (11227.6 ops/sec)\nDid 3751 RSA 4096 private key parse operations in 1055083us (3555.2 ops/sec)\n\nAfter:\nDid 1152 RSA 2048 signing operations in 1019638us (1129.8 ops/sec) [+13.8%]\nDid 52000 RSA 2048 verify (same key) operations in 1008049us (51584.8 ops/sec) [+15.1%]\nDid 47000 RSA 2048 verify (fresh key) operations in 1017770us (46179.4 ops/sec) [+14.0%]\nDid 10829 RSA 2048 private key parse operations in 1048927us (10323.9 ops/sec) [+1.0%]\nDid 442 RSA 3072 signing operations in 1064619us (415.2 ops/sec) [+5.1%]\nDid 24000 RSA 3072 verify (same key) operations in 1026170us (23387.9 ops/sec) [+1.5%]\nDid 22000 RSA 3072 verify (fresh key) operations in 1024522us (21473.4 ops/sec) [+1.4%]\nDid 5472 RSA 3072 private key parse operations in 1032525us (5299.6 ops/sec) [-0.1%]\nDid 192 RSA 4096 signing operations in 1014930us (189.2 ops/sec) [+14.7%]\nDid 14000 RSA 4096 verify (same key) operations in 1070762us (13074.8 ops/sec) [+7.9%]\nDid 13000 RSA 4096 verify (fresh key) operations in 1076995us (12070.6 ops/sec) [+7.5%]\nDid 3806 RSA 4096 private key parse operations in 1069780us (3557.7 ops/sec) [+0.1%]\n\nIntel(R) Xeon(R) Gold 6154 CPU @ 3.00GHz, OPENSSL_NO_ASM\nBefore:\nDid 760 RSA 2048 signing operations in 1007864us (754.1 ops/sec)\nDid 36000 RSA 2048 verify (same key) operations in 1015915us (35436.0 ops/sec)\nDid 32000 RSA 2048 verify (fresh key) operations in 1002094us (31933.1 ops/sec)\nDid 9812 RSA 2048 private key parse operations in 1030069us (9525.6 ops/sec)\nDid 264 RSA 3072 signing operations in 1011794us (260.9 ops/sec)\nDid 18000 RSA 3072 verify (same key) operations in 1054096us (17076.2 ops/sec)\nDid 16000 RSA 3072 verify (fresh key) operations in 1042326us (15350.3 ops/sec)\nDid 5181 RSA 3072 private key parse operations in 1052445us (4922.8 ops/sec)\nDid 132 RSA 4096 signing operations in 1048017us (126.0 ops/sec)\nDid 11000 RSA 4096 verify (same key) operations in 1072348us (10257.9 ops/sec)\nDid 10080 RSA 4096 verify (fresh key) operations in 1087489us (9269.1 ops/sec)\nDid 3157 RSA 4096 private key parse operations in 1080304us (2922.3 ops/sec)\n\nAfter:\nDid 741 RSA 2048 signing operations in 1001629us (739.8 ops/sec) [-1.9%]\nDid 36000 RSA 2048 verify (same key) operations in 1000102us (35996.3 ops/sec) [+1.6%]\nDid 33000 RSA 2048 verify (fresh key) operations in 1031105us (32004.5 ops/sec) [+0.2%]\nDid 9724 RSA 2048 private key parse operations in 1019805us (9535.2 ops/sec) [+0.1%]\nDid 276 RSA 3072 signing operations in 1005262us (274.6 ops/sec) [+5.2%]\nDid 17000 RSA 3072 verify (same key) operations in 1007153us (16879.3 ops/sec) [-1.2%]\nDid 16000 RSA 3072 verify (fresh key) operations in 1012666us (15799.9 ops/sec) [+2.9%]\nDid 5280 RSA 3072 private key parse operations in 1077362us (4900.9 ops/sec) [-0.4%]\nDid 132 RSA 4096 signing operations in 1039495us (127.0 ops/sec) [+0.8%]\nDid 11000 RSA 4096 verify (same key) operations in 1086299us (10126.1 ops/sec) [-1.3%]\nDid 9559 RSA 4096 verify (fresh key) operations in 1031203us (9269.8 ops/sec) [+0.0%]\nDid 3201 RSA 4096 private key parse operations in 1094303us (2925.1 ops/sec) [+0.1%]\n\nBug: 42290433\nChange-Id: I774c8c3af57d0d3aed95272b86b1c6f9c64ccce7\nReviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/77567\nAuto-Submit: David Benjamin \u003cdavidben@google.com\u003e\nReviewed-by: Bob Beck \u003cbbe@google.com\u003e\nCommit-Queue: David Benjamin \u003cdavidben@google.com\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "6dc8d5201811aaf62839996cc1642037fe910792",
      "old_mode": 33188,
      "old_path": "crypto/fipsmodule/bn/mul.cc.inc",
      "new_id": "f28e140764f8068459bfd0de993a5bbe5f2f4dbd",
      "new_mode": 33188,
      "new_path": "crypto/fipsmodule/bn/mul.cc.inc"
    }
  ]
}