[refactor] Use a lookup table rather than binary search for algorithm normalization.

Source/modules/crypto/NormalizeAlgorithm.cpp

Index: Source/modules/crypto/NormalizeAlgorithm.cpp
diff --git a/Source/modules/crypto/NormalizeAlgorithm.cpp b/Source/modules/crypto/NormalizeAlgorithm.cpp
index 8da1b28511c2020c22ab7626248803c91617ee33..2e4c48ef9b1e38b8db6ad4278b3c697ee90df40c 100644
--- a/Source/modules/crypto/NormalizeAlgorithm.cpp
+++ b/Source/modules/crypto/NormalizeAlgorithm.cpp
@@ -60,14 +60,6 @@ struct AlgorithmNameMapping {
 #endif
 };
 
-struct OperationParamsMapping {
-    blink::WebCryptoAlgorithmId algorithmId;
-    AlgorithmOperation operation;
-    blink::WebCryptoAlgorithmParamsType params;
-
-    bool operator<(const OperationParamsMapping&) const;
-};
-
 // Must be sorted by length, and then by reverse string.
 // Also all names must be upper case ASCII.
 const AlgorithmNameMapping algorithmNameMappings[] = {
@@ -84,66 +76,215 @@ const AlgorithmNameMapping algorithmNameMappings[] = {
     {"RSASSA-PKCS1-V1_5", 17, blink::WebCryptoAlgorithmIdRsaSsaPkcs1v1_5},
 };
 
-// What operations each algorithm supports, and what parameters it expects.
-// Must be sorted by algorithm id and then operation.
-const OperationParamsMapping operationParamsMappings[] = {
-    // AES-CBC
-    {blink::WebCryptoAlgorithmIdAesCbc, Encrypt, blink::WebCryptoAlgorithmParamsTypeAesCbcParams},
-    {blink::WebCryptoAlgorithmIdAesCbc, Decrypt, blink::WebCryptoAlgorithmParamsTypeAesCbcParams},
-    {blink::WebCryptoAlgorithmIdAesCbc, GenerateKey, blink::WebCryptoAlgorithmParamsTypeAesKeyGenParams},
-    {blink::WebCryptoAlgorithmIdAesCbc, ImportKey, blink::WebCryptoAlgorithmParamsTypeNone},
-    {blink::WebCryptoAlgorithmIdAesCbc, WrapKey, blink::WebCryptoAlgorithmParamsTypeAesCbcParams},
-    {blink::WebCryptoAlgorithmIdAesCbc, UnwrapKey, blink::WebCryptoAlgorithmParamsTypeAesCbcParams},
-
-    // HMAC
-    {blink::WebCryptoAlgorithmIdHmac, Sign, blink::WebCryptoAlgorithmParamsTypeNone},
-    {blink::WebCryptoAlgorithmIdHmac, Verify, blink::WebCryptoAlgorithmParamsTypeNone},
-    {blink::WebCryptoAlgorithmIdHmac, GenerateKey, blink::WebCryptoAlgorithmParamsTypeHmacKeyGenParams},
-    {blink::WebCryptoAlgorithmIdHmac, ImportKey, blink::WebCryptoAlgorithmParamsTypeHmacImportParams},
-
-    // RSASSA-PKCS1-v1_5
-    {blink::WebCryptoAlgorithmIdRsaSsaPkcs1v1_5, Sign, blink::WebCryptoAlgorithmParamsTypeNone},
-    {blink::WebCryptoAlgorithmIdRsaSsaPkcs1v1_5, Verify, blink::WebCryptoAlgorithmParamsTypeNone},
-    {blink::WebCryptoAlgorithmIdRsaSsaPkcs1v1_5, GenerateKey, blink::WebCryptoAlgorithmParamsTypeRsaHashedKeyGenParams},
-    {blink::WebCryptoAlgorithmIdRsaSsaPkcs1v1_5, ImportKey, blink::WebCryptoAlgorithmParamsTypeRsaHashedImportParams},
-
-    // RSAES-PKCS1-v1_5
-    {blink::WebCryptoAlgorithmIdRsaEsPkcs1v1_5, Encrypt, blink::WebCryptoAlgorithmParamsTypeNone},
-    {blink::WebCryptoAlgorithmIdRsaEsPkcs1v1_5, Decrypt, blink::WebCryptoAlgorithmParamsTypeNone},
-    {blink::WebCryptoAlgorithmIdRsaEsPkcs1v1_5, GenerateKey, blink::WebCryptoAlgorithmParamsTypeRsaKeyGenParams},
-    {blink::WebCryptoAlgorithmIdRsaEsPkcs1v1_5, ImportKey, blink::WebCryptoAlgorithmParamsTypeNone},
-    {blink::WebCryptoAlgorithmIdRsaEsPkcs1v1_5, WrapKey, blink::WebCryptoAlgorithmParamsTypeNone},
-    {blink::WebCryptoAlgorithmIdRsaEsPkcs1v1_5, UnwrapKey, blink::WebCryptoAlgorithmParamsTypeNone},
-
-    // SHA-*
-    {blink::WebCryptoAlgorithmIdSha1, Digest, blink::WebCryptoAlgorithmParamsTypeNone},
-    {blink::WebCryptoAlgorithmIdSha256, Digest, blink::WebCryptoAlgorithmParamsTypeNone},
-    {blink::WebCryptoAlgorithmIdSha384, Digest, blink::WebCryptoAlgorithmParamsTypeNone},
-    {blink::WebCryptoAlgorithmIdSha512, Digest, blink::WebCryptoAlgorithmParamsTypeNone},
-
-    // AES-GCM
-    {blink::WebCryptoAlgorithmIdAesGcm, Encrypt, blink::WebCryptoAlgorithmParamsTypeAesGcmParams},
-    {blink::WebCryptoAlgorithmIdAesGcm, Decrypt, blink::WebCryptoAlgorithmParamsTypeAesGcmParams},
-    {blink::WebCryptoAlgorithmIdAesGcm, GenerateKey, blink::WebCryptoAlgorithmParamsTypeAesKeyGenParams},
-    {blink::WebCryptoAlgorithmIdAesGcm, ImportKey, blink::WebCryptoAlgorithmParamsTypeNone},
-    {blink::WebCryptoAlgorithmIdAesGcm, WrapKey, blink::WebCryptoAlgorithmParamsTypeAesGcmParams},
-    {blink::WebCryptoAlgorithmIdAesGcm, UnwrapKey, blink::WebCryptoAlgorithmParamsTypeAesGcmParams},
-
-    // AES-CTR
-    {blink::WebCryptoAlgorithmIdAesCtr, Encrypt, blink::WebCryptoAlgorithmParamsTypeAesCtrParams},
-    {blink::WebCryptoAlgorithmIdAesCtr, Decrypt, blink::WebCryptoAlgorithmParamsTypeAesCtrParams},
-    {blink::WebCryptoAlgorithmIdAesCtr, GenerateKey, blink::WebCryptoAlgorithmParamsTypeAesKeyGenParams},
-    {blink::WebCryptoAlgorithmIdAesCtr, ImportKey, blink::WebCryptoAlgorithmParamsTypeNone},
-    {blink::WebCryptoAlgorithmIdAesCtr, WrapKey, blink::WebCryptoAlgorithmParamsTypeAesCtrParams},
-    {blink::WebCryptoAlgorithmIdAesCtr, UnwrapKey, blink::WebCryptoAlgorithmParamsTypeAesCtrParams},
-
-    // AES-KW
-    {blink::WebCryptoAlgorithmIdAesKw, GenerateKey, blink::WebCryptoAlgorithmParamsTypeAesKeyGenParams},
-    {blink::WebCryptoAlgorithmIdAesKw, ImportKey, blink::WebCryptoAlgorithmParamsTypeNone},
-    {blink::WebCryptoAlgorithmIdAesKw, WrapKey, blink::WebCryptoAlgorithmParamsTypeNone},
-    {blink::WebCryptoAlgorithmIdAesKw, UnwrapKey, blink::WebCryptoAlgorithmParamsTypeNone},
+typedef char ParamsTypeOrUndefined;
+const ParamsTypeOrUndefined Undefined = -1;
+
+struct AlgorithmInfo {

[eroman, 2014/04/23 23:26:23]

Rather than introduce another switch statement on algorithmId, I decided to
store all the per-algorithm information in a static map. This big chunk of code
is re-formatting "operationParamsMapping" to a fixed array.

Although it is a harder to read/edit than before it has the advantage of:
  * Faster lookup time
  * Smaller static data size

+    // The canonical (case-sensitive) name for the algorithm.
+    const char* name;
+
+    // The full set of key usages allowed by the algorithm. In the case of
+    // asymmetric algorithms, it is the union of key usages for public and
+    // private keys.
+    blink::WebCryptoKeyUsageMask allKeyUsages;
+
+    // A map from the operation to the expected parameter type of the algorithm.
+    // If an operation is not applicable for the algorithm, set to Undefined.
+    const ParamsTypeOrUndefined operationToParamsType[LastAlgorithmOperation + 1];
+};
+
+// A mapping from the algorithm ID to information about the algorithm.
+const AlgorithmInfo algorithmIdToInfo[] = {
+    { // Index 0
+        "AES-CBC",

[eroman, 2014/04/23 23:26:23]

The names were moved from algorithmIdToName().

+        blink::WebCryptoKeyUsageEncrypt | blink::WebCryptoKeyUsageDecrypt | blink::WebCryptoKeyUsageWrapKey | blink::WebCryptoKeyUsageUnwrapKey, {
+            blink::WebCryptoAlgorithmParamsTypeAesCbcParams, // Encrypt
+            blink::WebCryptoAlgorithmParamsTypeAesCbcParams, // Decrypt
+            Undefined, // Sign
+            Undefined, // Verify
+            Undefined, // Digest
+            blink::WebCryptoAlgorithmParamsTypeAesKeyGenParams, // GenerateKey
+            blink::WebCryptoAlgorithmParamsTypeNone, // ImportKey
+            Undefined, // DeriveKey
+            blink::WebCryptoAlgorithmParamsTypeAesCbcParams, // WrapKey
+            blink::WebCryptoAlgorithmParamsTypeAesCbcParams // UnwrapKey
+        }
+    }, { // Index 1
+        "HMAC",
+        blink::WebCryptoKeyUsageSign | blink::WebCryptoKeyUsageVerify, {
+            Undefined, // Encrypt
+            Undefined, // Decrypt
+            blink::WebCryptoAlgorithmParamsTypeNone, // Sign
+            blink::WebCryptoAlgorithmParamsTypeNone, // Verify
+            Undefined, // Digest
+            blink::WebCryptoAlgorithmParamsTypeHmacKeyGenParams, // GenerateKey
+            blink::WebCryptoAlgorithmParamsTypeHmacImportParams, // ImportKey
+            Undefined, // DeriveKey
+            Undefined, // WrapKey
+            Undefined // UnwrapKey
+        }
+    }, { // Index 2
+        "RSASSA-PKCS1-v1_5",
+        blink::WebCryptoKeyUsageSign | blink::WebCryptoKeyUsageVerify, {
+            Undefined, // Encrypt
+            Undefined, // Decrypt
+            blink::WebCryptoAlgorithmParamsTypeNone, // Sign
+            blink::WebCryptoAlgorithmParamsTypeNone, // Verify
+            Undefined, // Digest
+            blink::WebCryptoAlgorithmParamsTypeRsaHashedKeyGenParams, // GenerateKey
+            blink::WebCryptoAlgorithmParamsTypeRsaHashedImportParams, // ImportKey
+            Undefined, // DeriveKey
+            Undefined, // WrapKey
+            Undefined // UnwrapKey
+        }
+    }, { // Index 3
+        "RSAES-PKCS1-v1_5",
+        blink::WebCryptoKeyUsageEncrypt | blink::WebCryptoKeyUsageDecrypt | blink::WebCryptoKeyUsageWrapKey | blink::WebCryptoKeyUsageUnwrapKey, {
+            blink::WebCryptoAlgorithmParamsTypeNone, // Encrypt
+            blink::WebCryptoAlgorithmParamsTypeNone, // Decrypt
+            Undefined, // Sign
+            Undefined, // Verify
+            Undefined, // Digest
+            blink::WebCryptoAlgorithmParamsTypeRsaKeyGenParams, // GenerateKey
+            blink::WebCryptoAlgorithmParamsTypeNone, // ImportKey
+            Undefined, // DeriveKey
+            blink::WebCryptoAlgorithmParamsTypeNone, // WrapKey
+            blink::WebCryptoAlgorithmParamsTypeNone // UnwrapKey
+        }
+    }, { // Index 4
+        "SHA-1",
+        0, {
+            Undefined, // Encrypt
+            Undefined, // Decrypt
+            Undefined, // Sign
+            Undefined, // Verify
+            blink::WebCryptoAlgorithmParamsTypeNone, // Digest
+            Undefined, // GenerateKey
+            Undefined, // ImportKey
+            Undefined, // DeriveKey
+            Undefined, // WrapKey
+            Undefined // UnwrapKey
+        }
+    }, { // Index 5
+        "SHA-256",
+        0, {
+            Undefined, // Encrypt
+            Undefined, // Decrypt
+            Undefined, // Sign
+            Undefined, // Verify
+            blink::WebCryptoAlgorithmParamsTypeNone, // Digest
+            Undefined, // GenerateKey
+            Undefined, // ImportKey
+            Undefined, // DeriveKey
+            Undefined, // WrapKey
+            Undefined // UnwrapKey
+        }
+    }, { // Index 6
+        "SHA-384",
+        0, {
+            Undefined, // Encrypt
+            Undefined, // Decrypt
+            Undefined, // Sign
+            Undefined, // Verify
+            blink::WebCryptoAlgorithmParamsTypeNone, // Digest
+            Undefined, // GenerateKey
+            Undefined, // ImportKey
+            Undefined, // DeriveKey
+            Undefined, // WrapKey
+            Undefined // UnwrapKey
+        }
+    }, { // Index 7
+        "SHA-512",
+        0, {
+            Undefined, // Encrypt
+            Undefined, // Decrypt
+            Undefined, // Sign
+            Undefined, // Verify
+            blink::WebCryptoAlgorithmParamsTypeNone, // Digest
+            Undefined, // GenerateKey
+            Undefined, // ImportKey
+            Undefined, // DeriveKey
+            Undefined, // WrapKey
+            Undefined // UnwrapKey
+        }
+    }, { // Index 8
+        "AES-GCM",
+        blink::WebCryptoKeyUsageEncrypt | blink::WebCryptoKeyUsageDecrypt | blink::WebCryptoKeyUsageWrapKey | blink::WebCryptoKeyUsageUnwrapKey, {
+            blink::WebCryptoAlgorithmParamsTypeAesGcmParams, // Encrypt
+            blink::WebCryptoAlgorithmParamsTypeAesGcmParams, // Decrypt
+            Undefined, // Sign
+            Undefined, // Verify
+            Undefined, // Digest
+            blink::WebCryptoAlgorithmParamsTypeAesKeyGenParams, // GenerateKey
+            blink::WebCryptoAlgorithmParamsTypeNone, // ImportKey
+            Undefined, // DeriveKey
+            blink::WebCryptoAlgorithmParamsTypeAesGcmParams, // WrapKey
+            blink::WebCryptoAlgorithmParamsTypeAesGcmParams // UnwrapKey
+        }
+    }, { // Index 9
+        "RSA-OAEP",
+        blink::WebCryptoKeyUsageEncrypt | blink::WebCryptoKeyUsageDecrypt | blink::WebCryptoKeyUsageWrapKey | blink::WebCryptoKeyUsageUnwrapKey, {
+            // FIXME:
+            Undefined, // Encrypt
+            Undefined, // Decrypt
+            Undefined, // Sign
+            Undefined, // Verify
+            Undefined, // Digest
+            Undefined, // GenerateKey
+            Undefined, // ImportKey
+            Undefined, // DeriveKey
+            Undefined, // WrapKey
+            Undefined // UnwrapKey
+        }
+    }, { // Index 10
+        "AES-CTR",
+        blink::WebCryptoKeyUsageEncrypt | blink::WebCryptoKeyUsageDecrypt | blink::WebCryptoKeyUsageWrapKey | blink::WebCryptoKeyUsageUnwrapKey, {
+            blink::WebCryptoAlgorithmParamsTypeAesCtrParams, // Encrypt
+            blink::WebCryptoAlgorithmParamsTypeAesCtrParams, // Decrypt
+            Undefined, // Sign
+            Undefined, // Verify
+            Undefined, // Digest
+            blink::WebCryptoAlgorithmParamsTypeAesKeyGenParams, // GenerateKey
+            blink::WebCryptoAlgorithmParamsTypeNone, // ImportKey
+            Undefined, // DeriveKey
+            blink::WebCryptoAlgorithmParamsTypeAesCtrParams, // WrapKey
+            blink::WebCryptoAlgorithmParamsTypeAesCtrParams // UnwrapKey
+        }
+    }, { // Index 11
+        "AES-KW",
+        blink::WebCryptoKeyUsageWrapKey | blink::WebCryptoKeyUsageUnwrapKey, {
+            Undefined, // Encrypt
+            Undefined, // Decrypt
+            Undefined, // Sign
+            Undefined, // Verify
+            Undefined, // Digest
+            blink::WebCryptoAlgorithmParamsTypeAesKeyGenParams, // GenerateKey
+            blink::WebCryptoAlgorithmParamsTypeNone, // ImportKey
+            Undefined, // DeriveKey
+            blink::WebCryptoAlgorithmParamsTypeNone, // WrapKey
+            blink::WebCryptoAlgorithmParamsTypeNone // UnwrapKey
+        }
+    },
 };
 
+// Initializing the algorithmIdToInfo table above depends on knowing the enum
+// values for algorithm IDs. If those ever change, the table will need to be
+// updated.
+COMPILE_ASSERT(blink::WebCryptoAlgorithmIdAesCbc == 0, AesCbc_idDoesntMatch);
+COMPILE_ASSERT(blink::WebCryptoAlgorithmIdHmac == 1, Hmac_idDoesntMatch);
+COMPILE_ASSERT(blink::WebCryptoAlgorithmIdRsaSsaPkcs1v1_5 == 2, RsaSsaPkcs1v1_5_idDoesntMatch);
+COMPILE_ASSERT(blink::WebCryptoAlgorithmIdRsaEsPkcs1v1_5 == 3, RsaEsPkcs1v1_5_idDoesntMatch);
+COMPILE_ASSERT(blink::WebCryptoAlgorithmIdSha1 == 4, Sha1_idDoesntMatch);
+COMPILE_ASSERT(blink::WebCryptoAlgorithmIdSha256 == 5, Sha256_idDoesntMatch);
+COMPILE_ASSERT(blink::WebCryptoAlgorithmIdSha384 == 6, Sha384_idDoesntMatch);
+COMPILE_ASSERT(blink::WebCryptoAlgorithmIdSha512 == 7, Sha512_idDoesntMatch);
+COMPILE_ASSERT(blink::WebCryptoAlgorithmIdAesGcm == 8, AesGcm_idDoesntMatch);
+COMPILE_ASSERT(blink::WebCryptoAlgorithmIdRsaOaep == 9, RsaOaep_idDoesntMatch);
+COMPILE_ASSERT(blink::WebCryptoAlgorithmIdAesCtr == 10, AesCtr_idDoesntMatch);
+COMPILE_ASSERT(blink::WebCryptoAlgorithmIdAesKw == 11, AesKw_idDoesntMatch);
+COMPILE_ASSERT(blink::WebCryptoAlgorithmIdLast == 11, Last_idDoesntMatch);
+COMPILE_ASSERT(9 == LastAlgorithmOperation, UpdateParamsMapping);
+
 #if ASSERT_ENABLED
 
 // Essentially std::is_sorted() (however that function is new to C++11).
@@ -203,15 +344,6 @@ bool verifyAlgorithmNameMappings(const AlgorithmNameMapping* begin, const Algori
 }
 #endif
 
-bool OperationParamsMapping::operator<(const OperationParamsMapping& o) const
-{
-    if (algorithmId < o.algorithmId)
-        return true;
-    if (algorithmId > o.algorithmId)
-        return false;
-    return operation < o.operation;
-}
-
 template <typename CharType>
 bool algorithmNameComparator(const AlgorithmNameMapping& a, StringImpl* b)
 {
@@ -262,21 +394,11 @@ bool lookupAlgorithmIdByName(const String& algorithmName, blink::WebCryptoAlgori
     return true;
 }
 
-bool lookupAlgorithmParamsType(blink::WebCryptoAlgorithmId id, AlgorithmOperation op, blink::WebCryptoAlgorithmParamsType& paramsType)
+const AlgorithmInfo* lookupAlgorithmInfo(blink::WebCryptoAlgorithmId id)
 {
-    const OperationParamsMapping* begin = operationParamsMappings;
-    const OperationParamsMapping* end = operationParamsMappings + WTF_ARRAY_LENGTH(operationParamsMappings);
-
-    ASSERT(isSorted(begin, end));
-
-    OperationParamsMapping search = { id, op };
-    const OperationParamsMapping* it = std::lower_bound(begin, end, search);
-    if (it == end)
-        return false;
-    if (it->algorithmId != id || it->operation != op)
-        return false;
-    paramsType = it->params;
-    return true;
+    if (id < 0 || id >= WTF_ARRAY_LENGTH(algorithmIdToInfo))
+        return 0;
+    return &algorithmIdToInfo[id];
 }
 
 void completeWithSyntaxError(const String& message, CryptoResult* result)
@@ -795,13 +917,16 @@ bool parseAlgorithm(const Dictionary& raw, AlgorithmOperation op, blink::WebCryp
     // Remove the "Algorithm:" prefix for all subsequent errors.
     context.removeLast();
 
-    blink::WebCryptoAlgorithmParamsType paramsType;
-    if (!lookupAlgorithmParamsType(algorithmId, op, paramsType)) {
-        context.add(algorithmIdToName(algorithmId));
+    const AlgorithmInfo* algorithmInfo = lookupAlgorithmInfo(algorithmId);
+
+    if (algorithmInfo->operationToParamsType[op] == Undefined) {
+        context.add(algorithmInfo->name);
         completeWithNotSupportedError(context.toString("Unsupported operation", operationToString(op)), result);
         return false;
     }
 
+    blink::WebCryptoAlgorithmParamsType paramsType = static_cast<blink::WebCryptoAlgorithmParamsType>(algorithmInfo->operationToParamsType[op]);
+
     OwnPtr<blink::WebCryptoAlgorithmParams> params;
     if (!parseAlgorithmParams(raw, paramsType, params, context, result))
         return false;
@@ -819,33 +944,16 @@ bool parseAlgorithm(const Dictionary& raw, AlgorithmOperation op, blink::WebCryp
 
 const char* algorithmIdToName(blink::WebCryptoAlgorithmId id)
 {
-    switch (id) {
-    case blink::WebCryptoAlgorithmIdAesCbc:
-        return "AES-CBC";
-    case blink::WebCryptoAlgorithmIdAesCtr:
-        return "AES-CTR";
-    case blink::WebCryptoAlgorithmIdAesGcm:
-        return "AES-GCM";
-    case blink::WebCryptoAlgorithmIdHmac:
-        return "HMAC";
-    case blink::WebCryptoAlgorithmIdRsaSsaPkcs1v1_5:
-        return "RSASSA-PKCS1-v1_5";
-    case blink::WebCryptoAlgorithmIdRsaEsPkcs1v1_5:
-        return "RSAES-PKCS1-v1_5";
-    case blink::WebCryptoAlgorithmIdSha1:
-        return "SHA-1";
-    case blink::WebCryptoAlgorithmIdSha256:
-        return "SHA-256";
-    case blink::WebCryptoAlgorithmIdSha384:
-        return "SHA-384";
-    case blink::WebCryptoAlgorithmIdSha512:
-        return "SHA-512";
-    case blink::WebCryptoAlgorithmIdAesKw:
-        return "AES-KW";
-    case blink::WebCryptoAlgorithmIdRsaOaep:
-        return "RSA-OAEP";
+    return lookupAlgorithmInfo(id)->name;
+}
+
+bool verifyUsagesAreConsistentForAlgorithm(blink::WebCryptoAlgorithmId id, blink::WebCryptoKeyUsageMask keyUsages, CryptoResult* result)
+{
+    if ((keyUsages & lookupAlgorithmInfo(id)->allKeyUsages) != keyUsages) {
+        completeWithDataError("keyUsages contains values not applicable to the algorithm", result);
+        return false;
     }
-    return 0;
+    return true;
 }
 
 } // namespace WebCore