Refactorization: Faster calculation of CRC32 by avoiding to create a temporary string. Use proper types in checksum functions. (#4180)

PKEuS · web-flow · commit 4bd189c3c886 · 2022-06-08T16:55:06.000+02:00
Merged from LCppC
diff --git a/lib/preprocessor.cpp b/lib/preprocessor.cpp
@@ -1017,30 +1017,28 @@ static const std::uint32_t crc32Table[] = {
     0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
 };
 
-static std::uint32_t crc32(const std::string &data)
+static void crc32(const std::string &data, uint32_t& crc)
 {
-    std::uint32_t crc = ~0U;
     for (char c : data) {
         crc = crc32Table[(crc ^ (unsigned char)c) & 0xFF] ^ (crc >> 8);
     }
-    return crc ^ ~0U;
 }
 
-unsigned int Preprocessor::calculateChecksum(const simplecpp::TokenList &tokens1, const std::string &toolinfo) const
+uint32_t Preprocessor::calculateChecksum(const simplecpp::TokenList &tokens1, const std::string &toolinfo) const
 {
-    std::ostringstream ostr;
-    ostr << toolinfo << '\n';
+    std::uint32_t crc = ~0U;
+    crc32(toolinfo, crc);
     for (const simplecpp::Token *tok = tokens1.cfront(); tok; tok = tok->next) {
         if (!tok->comment)
-            ostr << tok->str();
+            crc32(tok->str(), crc);
     }
     for (std::map<std::string, simplecpp::TokenList *>::const_iterator it = mTokenLists.begin(); it != mTokenLists.end(); ++it) {
         for (const simplecpp::Token *tok = it->second->cfront(); tok; tok = tok->next) {
             if (!tok->comment)
-                ostr << tok->str();
+                crc32(tok->str(), crc);
         }
     }
-    return crc32(ostr.str());
+    return crc ^ ~0U;
 }
 
 void Preprocessor::simplifyPragmaAsm(simplecpp::TokenList *tokenList) const
diff --git a/lib/preprocessor.h b/lib/preprocessor.h
@@ -170,7 +170,7 @@ class CPPCHECKLIB Preprocessor {
      * @param toolinfo   Arbitrary extra toolinfo
      * @return CRC32 checksum
      */
-    unsigned int calculateChecksum(const simplecpp::TokenList &tokens1, const std::string &toolinfo) const;
+    uint32_t calculateChecksum(const simplecpp::TokenList &tokens1, const std::string &toolinfo) const;
 
     void simplifyPragmaAsm(simplecpp::TokenList *tokenList) const;
 
diff --git a/lib/tokenlist.cpp b/lib/tokenlist.cpp
@@ -460,20 +460,20 @@ void TokenList::createTokens(simplecpp::TokenList&& tokenList)
 
 //---------------------------------------------------------------------------
 
-unsigned long long TokenList::calculateChecksum() const
+uint64_t TokenList::calculateChecksum() const
 {
-    unsigned long long checksum = 0;
+    uint64_t checksum = 0;
     for (const Token* tok = front(); tok; tok = tok->next()) {
-        const unsigned int subchecksum1 = tok->flags() + tok->varId() + tok->tokType();
-        unsigned int subchecksum2 = 0;
+        const uint32_t subchecksum1 = tok->flags() + tok->varId() + tok->tokType();
+        uint32_t subchecksum2 = 0;
         for (char i : tok->str())
-            subchecksum2 += (unsigned int)i;
+            subchecksum2 += (uint32_t)i;
         if (!tok->originalName().empty()) {
             for (char i : tok->originalName())
-                subchecksum2 += (unsigned int) i;
+                subchecksum2 += (uint32_t)i;
         }
 
-        checksum ^= ((static_cast<unsigned long long>(subchecksum1) << 32) | subchecksum2);
+        checksum ^= ((static_cast<uint64_t>(subchecksum1) << 32) | subchecksum2);
 
         const bool bit1 = (checksum & 1) != 0;
         checksum >>= 1;
diff --git a/lib/tokenlist.h b/lib/tokenlist.h
@@ -156,7 +156,7 @@ class CPPCHECKLIB TokenList {
      * Calculates a 64-bit checksum of the token list used to compare
      * multiple token lists with each other as quickly as possible.
      */
-    unsigned long long calculateChecksum() const;
+    uint64_t calculateChecksum() const;
 
     /**
      * Create abstract syntax tree.

Original file line number	Diff line number	Diff line change
`@@ -1017,30 +1017,28 @@ static const std::uint32_t crc32Table[] = {`
`1017`	`1017`	`0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d`
`1018`	`1018`	`};`
`1019`	`1019`
`1020`		`-static std::uint32_t crc32(const std::string &data)`
	`1020`	`+static void crc32(const std::string &data, uint32_t& crc)`
`1021`	`1021`	`{`
`1022`		`- std::uint32_t crc = ~0U;`
`1023`	`1022`	`for (char c : data) {`
`1024`	`1023`	`crc = crc32Table[(crc ^ (unsigned char)c) & 0xFF] ^ (crc >> 8);`
`1025`	`1024`	`}`
`1026`		`- return crc ^ ~0U;`
`1027`	`1025`	`}`
`1028`	`1026`
`1029`		`-unsigned int Preprocessor::calculateChecksum(const simplecpp::TokenList &tokens1, const std::string &toolinfo) const`
	`1027`	`+uint32_t Preprocessor::calculateChecksum(const simplecpp::TokenList &tokens1, const std::string &toolinfo) const`
`1030`	`1028`	`{`
`1031`		`- std::ostringstream ostr;`
`1032`		`- ostr << toolinfo << '\n';`
	`1029`	`+ std::uint32_t crc = ~0U;`
	`1030`	`+ crc32(toolinfo, crc);`
`1033`	`1031`	`for (const simplecpp::Token *tok = tokens1.cfront(); tok; tok = tok->next) {`
`1034`	`1032`	`if (!tok->comment)`
`1035`		`- ostr << tok->str();`
	`1033`	`+ crc32(tok->str(), crc);`
`1036`	`1034`	`}`
`1037`	`1035`	`for (std::map<std::string, simplecpp::TokenList *>::const_iterator it = mTokenLists.begin(); it != mTokenLists.end(); ++it) {`
`1038`	`1036`	`for (const simplecpp::Token *tok = it->second->cfront(); tok; tok = tok->next) {`
`1039`	`1037`	`if (!tok->comment)`
`1040`		`- ostr << tok->str();`
	`1038`	`+ crc32(tok->str(), crc);`
`1041`	`1039`	`}`
`1042`	`1040`	`}`
`1043`		`- return crc32(ostr.str());`
	`1041`	`+ return crc ^ ~0U;`
`1044`	`1042`	`}`
`1045`	`1043`
`1046`	`1044`	`void Preprocessor::simplifyPragmaAsm(simplecpp::TokenList *tokenList) const`