Speed up constant-time base64 decoding.

I was inspired to look at this again recently and noticed we could do a
bit better. Instead of a tower of selects, rely on all the cases being
mutually exclusive and use the ret |= mask & value formulation without
loss in clarity. We do need to fixup the invalid case slightly, but
since that computation is mostly independent, I'm guessing the CPU and
compiler are able to schedule it effectively.

Before:
Did 251000 base64 decode operations in 2002569us (159.4 MB/sec)
After:
Did 346000 base64 decode operations in 2005426us (219.5 MB/sec) [+37.7%]

Change-Id: I542167202fd4e94c93dd5a2519a97bc388072c89
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/49525
Reviewed-by: Adam Langley <agl@google.com>

1 files changed, 45 insertions, 1 deletions

diff --git a/tool/speed.cc b/tool/speed.cc
index 613e630..b91a4ce 100644
--- a/tool/speed.cc
+++ b/tool/speed.cc
@@ -26,6 +26,7 @@
 
 #include <openssl/aead.h>
 #include <openssl/aes.h>
+#include <openssl/base64.h>
 #include <openssl/bn.h>
 #include <openssl/curve25519.h>
 #include <openssl/crypto.h>
@@ -992,6 +993,48 @@ static bool SpeedHashToCurve(const std::string &selected) {
   return true;
 }
 
+static bool SpeedBase64(const std::string &selected) {
+  if (!selected.empty() && selected.find("base64") == std::string::npos) {
+    return true;
+  }
+
+  static const char kInput[] =
+    "MIIDtTCCAp2gAwIBAgIJALW2IrlaBKUhMA0GCSqGSIb3DQEBCwUAMEUxCzAJBgNV"
+    "BAYTAkFVMRMwEQYDVQQIEwpTb21lLVN0YXRlMSEwHwYDVQQKExhJbnRlcm5ldCBX"
+    "aWRnaXRzIFB0eSBMdGQwHhcNMTYwNzA5MDQzODA5WhcNMTYwODA4MDQzODA5WjBF"
+    "MQswCQYDVQQGEwJBVTETMBEGA1UECBMKU29tZS1TdGF0ZTEhMB8GA1UEChMYSW50"
+    "ZXJuZXQgV2lkZ2l0cyBQdHkgTHRkMIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIB"
+    "CgKCAQEAugvahBkSAUF1fC49vb1bvlPrcl80kop1iLpiuYoz4Qptwy57+EWssZBc"
+    "HprZ5BkWf6PeGZ7F5AX1PyJbGHZLqvMCvViP6pd4MFox/igESISEHEixoiXCzepB"
+    "rhtp5UQSjHD4D4hKtgdMgVxX+LRtwgW3mnu/vBu7rzpr/DS8io99p3lqZ1Aky+aN"
+    "lcMj6MYy8U+YFEevb/V0lRY9oqwmW7BHnXikm/vi6sjIS350U8zb/mRzYeIs2R65"
+    "LUduTL50+UMgat9ocewI2dv8aO9Dph+8NdGtg8LFYyTTHcUxJoMr1PTOgnmET19W"
+    "JH4PrFwk7ZE1QJQQ1L4iKmPeQistuQIDAQABo4GnMIGkMB0GA1UdDgQWBBT5m6Vv"
+    "zYjVYHG30iBE+j2XDhUE8jB1BgNVHSMEbjBsgBT5m6VvzYjVYHG30iBE+j2XDhUE"
+    "8qFJpEcwRTELMAkGA1UEBhMCQVUxEzARBgNVBAgTClNvbWUtU3RhdGUxITAfBgNV"
+    "BAoTGEludGVybmV0IFdpZGdpdHMgUHR5IEx0ZIIJALW2IrlaBKUhMAwGA1UdEwQF"
+    "MAMBAf8wDQYJKoZIhvcNAQELBQADggEBAD7Jg68SArYWlcoHfZAB90Pmyrt5H6D8"
+    "LRi+W2Ri1fBNxREELnezWJ2scjl4UMcsKYp4Pi950gVN+62IgrImcCNvtb5I1Cfy"
+    "/MNNur9ffas6X334D0hYVIQTePyFk3umI+2mJQrtZZyMPIKSY/sYGQHhGGX6wGK+"
+    "GO/og0PQk/Vu6D+GU2XRnDV0YZg1lsAsHd21XryK6fDmNkEMwbIWrts4xc7scRrG"
+    "HWy+iMf6/7p/Ak/SIicM4XSwmlQ8pPxAZPr+E2LoVd9pMpWUwpW2UbtO5wsGTrY5"
+    "sO45tFNN/y+jtUheB1C2ijObG/tXELaiyCdM+S/waeuv0MXtI4xnn1A=";
+
+  std::vector<uint8_t> out(strlen(kInput));
+  size_t len;
+  TimeResults results;
+  if (!TimeFunction(&results, [&]() -> bool {
+        return EVP_DecodeBase64(out.data(), &len, out.size(),
+                                reinterpret_cast<const uint8_t *>(kInput),
+                                strlen(kInput));
+      })) {
+    fprintf(stderr, "base64 decode failed.\n");
+    return false;
+  }
+  results.PrintWithBytes("base64 decode", strlen(kInput));
+  return true;
+}
+
 static TRUST_TOKEN_PRETOKEN *trust_token_pretoken_dup(
     TRUST_TOKEN_PRETOKEN *in) {
   TRUST_TOKEN_PRETOKEN *out =
@@ -1390,7 +1433,8 @@ bool Speed(const std::vector<std::string> &args) {
       !SpeedTrustToken("TrustToken-Exp2PMB-Batch1",
                        TRUST_TOKEN_experiment_v2_pmb(), 1, selected) ||
       !SpeedTrustToken("TrustToken-Exp2PMB-Batch10",
-                       TRUST_TOKEN_experiment_v2_pmb(), 10, selected)) {
+                       TRUST_TOKEN_experiment_v2_pmb(), 10, selected) ||
+      !SpeedBase64(selected)) {
     return false;
   }
 #if defined(BORINGSSL_FIPS)