diff options
author | Karen Arutyunov <karen@codesynthesis.com> | 2019-04-05 10:30:58 +0300 |
---|---|---|
committer | Karen Arutyunov <karen@codesynthesis.com> | 2019-04-05 17:53:59 +0300 |
commit | 72e7f011b29998d8a3e15eb5b381ef962af5fe5b (patch) | |
tree | 9fd87a0c6f545552849f466b20d3969a21e21e15 /mysql/extra/yassl/taocrypt/src/algebra.cpp | |
parent | 4e0bcdb33411afb02d60b72cbffa278344a572a6 (diff) |
Upgrade to 8.0.15
Diffstat (limited to 'mysql/extra/yassl/taocrypt/src/algebra.cpp')
-rw-r--r-- | mysql/extra/yassl/taocrypt/src/algebra.cpp | 336 |
1 files changed, 0 insertions, 336 deletions
diff --git a/mysql/extra/yassl/taocrypt/src/algebra.cpp b/mysql/extra/yassl/taocrypt/src/algebra.cpp deleted file mode 100644 index ace1704..0000000 --- a/mysql/extra/yassl/taocrypt/src/algebra.cpp +++ /dev/null @@ -1,336 +0,0 @@ -/* - Copyright (c) 2000, 2014, Oracle and/or its affiliates. All rights reserved. - - This program is free software; you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation; version 2 of the License. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA */ - -/* based on Wei Dai's algebra.cpp from CryptoPP */ -#undef NDEBUG -#define DEBUG // GCC 4.0 bug if NDEBUG and Optimize > 1 - -#include "runtime.hpp" -#include "algebra.hpp" -#ifdef USE_SYS_STL - #include <vector> -#else - #include "vector.hpp" -#endif - - -namespace STL = STL_NAMESPACE; - - -namespace TaoCrypt { - - -const Integer& AbstractGroup::Double(const Element &a) const -{ - return Add(a, a); -} - -const Integer& AbstractGroup::Subtract(const Element &a, const Element &b) const -{ - // make copy of a in case Inverse() overwrites it - Element a1(a); - return Add(a1, Inverse(b)); -} - -Integer& AbstractGroup::Accumulate(Element &a, const Element &b) const -{ - return a = Add(a, b); -} - -Integer& AbstractGroup::Reduce(Element &a, const Element &b) const -{ - return a = Subtract(a, b); -} - -const Integer& AbstractRing::Square(const Element &a) const -{ - return Multiply(a, a); -} - - -const Integer& AbstractRing::Divide(const Element &a, const Element &b) const -{ - // make copy of a in case MultiplicativeInverse() overwrites it - Element a1(a); - return Multiply(a1, MultiplicativeInverse(b)); -} - - -const Integer& AbstractEuclideanDomain::Mod(const Element &a, - const Element &b) const -{ - Element q; - DivisionAlgorithm(result, q, a, b); - return result; -} - -const Integer& AbstractEuclideanDomain::Gcd(const Element &a, - const Element &b) const -{ - STL::vector<Element> g(3); - g[0]= b; - g[1]= a; - unsigned int i0=0, i1=1, i2=2; - - while (!Equal(g[i1], this->Identity())) - { - g[i2] = Mod(g[i0], g[i1]); - unsigned int t = i0; i0 = i1; i1 = i2; i2 = t; - } - - return result = g[i0]; -} - - -Integer AbstractGroup::ScalarMultiply(const Element &base, - const Integer &exponent) const -{ - Element result; - SimultaneousMultiply(&result, base, &exponent, 1); - return result; -} - - -Integer AbstractGroup::CascadeScalarMultiply(const Element &x, - const Integer &e1, const Element &y, const Integer &e2) const -{ - const unsigned expLen = max(e1.BitCount(), e2.BitCount()); - if (expLen==0) - return Identity(); - - const unsigned w = (expLen <= 46 ? 1 : (expLen <= 260 ? 2 : 3)); - const unsigned tableSize = 1<<w; - STL::vector<Element> powerTable(tableSize << w); - - powerTable[1] = x; - powerTable[tableSize] = y; - if (w==1) - powerTable[3] = Add(x,y); - else - { - powerTable[2] = Double(x); - powerTable[2*tableSize] = Double(y); - - unsigned i, j; - - for (i=3; i<tableSize; i+=2) - powerTable[i] = Add(powerTable[i-2], powerTable[2]); - for (i=1; i<tableSize; i+=2) - for (j=i+tableSize; j<(tableSize<<w); j+=tableSize) - powerTable[j] = Add(powerTable[j-tableSize], y); - - for (i=3*tableSize; i<(tableSize<<w); i+=2*tableSize) - powerTable[i] = Add(powerTable[i-2*tableSize], - powerTable[2*tableSize]); - for (i=tableSize; i<(tableSize<<w); i+=2*tableSize) - for (j=i+2; j<i+tableSize; j+=2) - powerTable[j] = Add(powerTable[j-1], x); - } - - Element result; - unsigned power1 = 0, power2 = 0, prevPosition = expLen-1; - bool firstTime = true; - - for (int i = expLen-1; i>=0; i--) - { - power1 = 2*power1 + e1.GetBit(i); - power2 = 2*power2 + e2.GetBit(i); - - if (i==0 || 2*power1 >= tableSize || 2*power2 >= tableSize) - { - unsigned squaresBefore = prevPosition-i; - unsigned squaresAfter = 0; - prevPosition = i; - while ((power1 || power2) && power1%2 == 0 && power2%2==0) - { - power1 /= 2; - power2 /= 2; - squaresBefore--; - squaresAfter++; - } - if (firstTime) - { - result = powerTable[(power2<<w) + power1]; - firstTime = false; - } - else - { - while (squaresBefore--) - result = Double(result); - if (power1 || power2) - Accumulate(result, powerTable[(power2<<w) + power1]); - } - while (squaresAfter--) - result = Double(result); - power1 = power2 = 0; - } - } - return result; -} - - -struct WindowSlider -{ - WindowSlider(const Integer &exp, bool fastNegate, - unsigned int windowSizeIn=0) - : exp(exp), windowModulus(Integer::One()), windowSize(windowSizeIn), - windowBegin(0), fastNegate(fastNegate), firstTime(true), - finished(false) - { - if (windowSize == 0) - { - unsigned int expLen = exp.BitCount(); - windowSize = expLen <= 17 ? 1 : (expLen <= 24 ? 2 : - (expLen <= 70 ? 3 : (expLen <= 197 ? 4 : (expLen <= 539 ? 5 : - (expLen <= 1434 ? 6 : 7))))); - } - windowModulus <<= windowSize; - } - - void FindNextWindow() - { - unsigned int expLen = exp.WordCount() * WORD_BITS; - unsigned int skipCount = firstTime ? 0 : windowSize; - firstTime = false; - while (!exp.GetBit(skipCount)) - { - if (skipCount >= expLen) - { - finished = true; - return; - } - skipCount++; - } - - exp >>= skipCount; - windowBegin += skipCount; - expWindow = exp % (1 << windowSize); - - if (fastNegate && exp.GetBit(windowSize)) - { - negateNext = true; - expWindow = (1 << windowSize) - expWindow; - exp += windowModulus; - } - else - negateNext = false; - } - - Integer exp, windowModulus; - unsigned int windowSize, windowBegin, expWindow; - bool fastNegate, negateNext, firstTime, finished; -}; - - -void AbstractGroup::SimultaneousMultiply(Integer *results, const Integer &base, - const Integer *expBegin, unsigned int expCount) const -{ - STL::vector<STL::vector<Element> > buckets(expCount); - STL::vector<WindowSlider> exponents; - exponents.reserve(expCount); - unsigned int i; - - for (i=0; i<expCount; i++) - { - exponents.push_back(WindowSlider(*expBegin++, InversionIsFast(), 0)); - exponents[i].FindNextWindow(); - buckets[i].resize(1<<(exponents[i].windowSize-1), Identity()); - } - - unsigned int expBitPosition = 0; - Element g = base; - bool notDone = true; - - while (notDone) - { - notDone = false; - for (i=0; i<expCount; i++) - { - if (!exponents[i].finished && expBitPosition == - exponents[i].windowBegin) - { - Element &bucket = buckets[i][exponents[i].expWindow/2]; - if (exponents[i].negateNext) - Accumulate(bucket, Inverse(g)); - else - Accumulate(bucket, g); - exponents[i].FindNextWindow(); - } - notDone = notDone || !exponents[i].finished; - } - - if (notDone) - { - g = Double(g); - expBitPosition++; - } - } - - for (i=0; i<expCount; i++) - { - Element &r = *results++; - r = buckets[i][buckets[i].size()-1]; - if (buckets[i].size() > 1) - { - for (size_t j = buckets[i].size()-2; j >= 1; j--) - { - Accumulate(buckets[i][j], buckets[i][j+1]); - Accumulate(r, buckets[i][j]); - } - Accumulate(buckets[i][0], buckets[i][1]); - r = Add(Double(r), buckets[i][0]); - } - } -} - -Integer AbstractRing::Exponentiate(const Element &base, - const Integer &exponent) const -{ - Element result; - SimultaneousExponentiate(&result, base, &exponent, 1); - return result; -} - - -Integer AbstractRing::CascadeExponentiate(const Element &x, - const Integer &e1, const Element &y, const Integer &e2) const -{ - return MultiplicativeGroup().AbstractGroup::CascadeScalarMultiply( - x, e1, y, e2); -} - - -void AbstractRing::SimultaneousExponentiate(Integer *results, - const Integer &base, - const Integer *exponents, unsigned int expCount) const -{ - MultiplicativeGroup().AbstractGroup::SimultaneousMultiply(results, base, - exponents, expCount); -} - - -} // namespace - - -#ifdef HAVE_EXPLICIT_TEMPLATE_INSTANTIATION -namespace mySTL { -template TaoCrypt::WindowSlider* uninit_copy<TaoCrypt::WindowSlider*, TaoCrypt::WindowSlider*>(TaoCrypt::WindowSlider*, TaoCrypt::WindowSlider*, TaoCrypt::WindowSlider*); -template void destroy<TaoCrypt::WindowSlider*>(TaoCrypt::WindowSlider*, TaoCrypt::WindowSlider*); -template TaoCrypt::WindowSlider* GetArrayMemory<TaoCrypt::WindowSlider>(size_t); -template void FreeArrayMemory<TaoCrypt::WindowSlider>(TaoCrypt::WindowSlider*); -} -#endif - |