be/src/util/md5.cpp - doris - Git at Google


            
            // Licensed to the Apache Software Foundation (ASF) under one

            
            // or more contributor license agreements.  See the NOTICE file

            
            // distributed with this work for additional information

            
            // regarding copyright ownership.  The ASF licenses this file

            
            // to you under the Apache License, Version 2.0 (the

            
            // "License"); you may not use this file except in compliance

            
            // with the License.  You may obtain a copy of the License at

            
            //

            
            //   http://www.apache.org/licenses/LICENSE-2.0

            
            //

            
            // Unless required by applicable law or agreed to in writing,

            
            // software distributed under the License is distributed on an

            
            // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY

            
            // KIND, either express or implied.  See the License for the

            
            // specific language governing permissions and limitations

            
            // under the License.


            #include "util/md5.h"


            #include <algorithm>

            
            #include <cstring>

            
            #include <vector>


            #ifdef __AVX2__

            
            #include <immintrin.h>

            
            #endif


            #include "exec/common/endian.h"


            namespace doris {


            namespace {


            constexpr unsigned char MD5_DUMMY_INPUT = 0;


            void md5_to_hex(const unsigned char* digest, char* out) {

            
                static constexpr char DIGITS[] = "0123456789abcdef";

            
                for (int i = 0; i < MD5_DIGEST_LENGTH; ++i) {

            
                    *out++ = DIGITS[digest[i] >> 4];

            
                    *out++ = DIGITS[digest[i] & 0x0F];

            
                }

            
            }


            #ifdef __AVX2__


            constexpr uint32_t MD5_A0 = 0x67452301;

            
            constexpr uint32_t MD5_B0 = 0xefcdab89;

            
            constexpr uint32_t MD5_C0 = 0x98badcfe;

            
            constexpr uint32_t MD5_D0 = 0x10325476;


            size_t md5_num_blocks(size_t len) {

            
                return (len + 9 + 63) / 64;

            
            }


            size_t md5_pad_final_blocks(const unsigned char* data, size_t len, unsigned char* out) {

            
                size_t full_blocks = len / 64;

            
                size_t tail = len % 64;

            
                size_t num_blocks = md5_num_blocks(len);

            
                size_t final_count = num_blocks - full_blocks;


                std::memset(out, 0, final_count * 64);

            
                std::memcpy(out, data + full_blocks * 64, tail);

            
                out[tail] = 0x80;

            
                LittleEndian::Store64(out + final_count * 64 - 8, static_cast<uint64_t>(len) * 8);


                return final_count;

            
            }


            struct AVX2MD5Ops {

            
                using Vec = __m256i;

            
                static constexpr size_t LANES = 8;


                static Vec add(Vec a, Vec b) { return _mm256_add_epi32(a, b); }


                static Vec set1(uint32_t v) { return _mm256_set1_epi32(static_cast<int>(v)); }


                static Vec loadu(const void* p) {

            
                    return _mm256_loadu_si256(reinterpret_cast<const __m256i*>(p));

            
                }


                static void storeu(void* p, Vec v) { _mm256_storeu_si256(reinterpret_cast<__m256i*>(p), v); }


                template <int N>

            
                static Vec rotl(Vec x) {

            
                    return _mm256_or_si256(_mm256_slli_epi32(x, N), _mm256_srli_epi32(x, 32 - N));

            
                }


                static Vec F(Vec b, Vec c, Vec d) {

            
                    return _mm256_xor_si256(d, _mm256_and_si256(b, _mm256_xor_si256(c, d)));

            
                }


                static Vec G(Vec b, Vec c, Vec d) {

            
                    return _mm256_xor_si256(c, _mm256_and_si256(d, _mm256_xor_si256(b, c)));

            
                }


                static Vec H(Vec b, Vec c, Vec d) { return _mm256_xor_si256(b, _mm256_xor_si256(c, d)); }


                static Vec I(Vec b, Vec c, Vec d) {

            
                    return _mm256_xor_si256(c, _mm256_or_si256(b, _mm256_xor_si256(d, _mm256_set1_epi32(-1))));

            
                }


                static void gather_all_message_words(const unsigned char* const block_ptrs[], Vec msg[16]) {

            
                    for (int half = 0; half < 2; ++half) {

            
                        size_t off = half * 32;

            
                        Vec r0 = loadu(block_ptrs[0] + off);

            
                        Vec r1 = loadu(block_ptrs[1] + off);

            
                        Vec r2 = loadu(block_ptrs[2] + off);

            
                        Vec r3 = loadu(block_ptrs[3] + off);

            
                        Vec r4 = loadu(block_ptrs[4] + off);

            
                        Vec r5 = loadu(block_ptrs[5] + off);

            
                        Vec r6 = loadu(block_ptrs[6] + off);

            
                        Vec r7 = loadu(block_ptrs[7] + off);


                        Vec t0 = _mm256_unpacklo_epi32(r0, r1);

            
                        Vec t1 = _mm256_unpackhi_epi32(r0, r1);

            
                        Vec t2 = _mm256_unpacklo_epi32(r2, r3);

            
                        Vec t3 = _mm256_unpackhi_epi32(r2, r3);

            
                        Vec t4 = _mm256_unpacklo_epi32(r4, r5);

            
                        Vec t5 = _mm256_unpackhi_epi32(r4, r5);

            
                        Vec t6 = _mm256_unpacklo_epi32(r6, r7);

            
                        Vec t7 = _mm256_unpackhi_epi32(r6, r7);


                        Vec u0 = _mm256_unpacklo_epi64(t0, t2);

            
                        Vec u1 = _mm256_unpackhi_epi64(t0, t2);

            
                        Vec u2 = _mm256_unpacklo_epi64(t1, t3);

            
                        Vec u3 = _mm256_unpackhi_epi64(t1, t3);

            
                        Vec u4 = _mm256_unpacklo_epi64(t4, t6);

            
                        Vec u5 = _mm256_unpackhi_epi64(t4, t6);

            
                        Vec u6 = _mm256_unpacklo_epi64(t5, t7);

            
                        Vec u7 = _mm256_unpackhi_epi64(t5, t7);


                        size_t base = half * 8;

            
                        msg[base + 0] = _mm256_permute2x128_si256(u0, u4, 0x20);

            
                        msg[base + 4] = _mm256_permute2x128_si256(u0, u4, 0x31);

            
                        msg[base + 1] = _mm256_permute2x128_si256(u1, u5, 0x20);

            
                        msg[base + 5] = _mm256_permute2x128_si256(u1, u5, 0x31);

            
                        msg[base + 2] = _mm256_permute2x128_si256(u2, u6, 0x20);

            
                        msg[base + 6] = _mm256_permute2x128_si256(u2, u6, 0x31);

            
                        msg[base + 3] = _mm256_permute2x128_si256(u3, u7, 0x20);

            
                        msg[base + 7] = _mm256_permute2x128_si256(u3, u7, 0x31);

            
                    }

            
                }

            
            };


            #define MD5_STEP_X2(func, w1, x1, y1, z1, w2, x2, y2, z2, g, s, ti) \

            
                {                                                               \

            
                    Vec t1 = Ops::func(x1, y1, z1);                             \

            
                    Vec t2 = Ops::func(x2, y2, z2);                             \

            
                    t1 = Ops::add(t1, w1);                                      \

            
                    t2 = Ops::add(t2, w2);                                      \

            
                    Vec k = Ops::set1(ti);                                      \

            
                    t1 = Ops::add(t1, k);                                       \

            
                    t2 = Ops::add(t2, k);                                       \

            
                    t1 = Ops::add(t1, msg1[g]);                                 \

            
                    t2 = Ops::add(t2, msg2[g]);                                 \

            
                    (w1) = Ops::add(x1, Ops::template rotl<s>(t1));             \

            
                    (w2) = Ops::add(x2, Ops::template rotl<s>(t2));             \

            
                }


            template <typename Ops>

            
            struct MD5X2State {

            
                typename Ops::Vec a1, b1, c1, d1, a2, b2, c2, d2;

            
            };


            template <typename Ops>

            
            MD5X2State<Ops> md5_multi_buffer_block_x2(typename Ops::Vec a1, typename Ops::Vec b1,

            
                                                      typename Ops::Vec c1, typename Ops::Vec d1,

            
                                                      typename Ops::Vec a2, typename Ops::Vec b2,

            
                                                      typename Ops::Vec c2, typename Ops::Vec d2,

            
                                                      const typename Ops::Vec msg1[16],

            
                                                      const typename Ops::Vec msg2[16]) {

            
                using Vec = typename Ops::Vec;

            
                Vec aa1 = a1;

            
                Vec bb1 = b1;

            
                Vec cc1 = c1;

            
                Vec dd1 = d1;

            
                Vec aa2 = a2;

            
                Vec bb2 = b2;

            
                Vec cc2 = c2;

            
                Vec dd2 = d2;


                MD5_STEP_X2(F, a1, b1, c1, d1, a2, b2, c2, d2, 0, 7, 0xd76aa478)

            
                MD5_STEP_X2(F, d1, a1, b1, c1, d2, a2, b2, c2, 1, 12, 0xe8c7b756)

            
                MD5_STEP_X2(F, c1, d1, a1, b1, c2, d2, a2, b2, 2, 17, 0x242070db)

            
                MD5_STEP_X2(F, b1, c1, d1, a1, b2, c2, d2, a2, 3, 22, 0xc1bdceee)

            
                MD5_STEP_X2(F, a1, b1, c1, d1, a2, b2, c2, d2, 4, 7, 0xf57c0faf)

            
                MD5_STEP_X2(F, d1, a1, b1, c1, d2, a2, b2, c2, 5, 12, 0x4787c62a)

            
                MD5_STEP_X2(F, c1, d1, a1, b1, c2, d2, a2, b2, 6, 17, 0xa8304613)

            
                MD5_STEP_X2(F, b1, c1, d1, a1, b2, c2, d2, a2, 7, 22, 0xfd469501)

            
                MD5_STEP_X2(F, a1, b1, c1, d1, a2, b2, c2, d2, 8, 7, 0x698098d8)

            
                MD5_STEP_X2(F, d1, a1, b1, c1, d2, a2, b2, c2, 9, 12, 0x8b44f7af)

            
                MD5_STEP_X2(F, c1, d1, a1, b1, c2, d2, a2, b2, 10, 17, 0xffff5bb1)

            
                MD5_STEP_X2(F, b1, c1, d1, a1, b2, c2, d2, a2, 11, 22, 0x895cd7be)

            
                MD5_STEP_X2(F, a1, b1, c1, d1, a2, b2, c2, d2, 12, 7, 0x6b901122)

            
                MD5_STEP_X2(F, d1, a1, b1, c1, d2, a2, b2, c2, 13, 12, 0xfd987193)

            
                MD5_STEP_X2(F, c1, d1, a1, b1, c2, d2, a2, b2, 14, 17, 0xa679438e)

            
                MD5_STEP_X2(F, b1, c1, d1, a1, b2, c2, d2, a2, 15, 22, 0x49b40821)


                MD5_STEP_X2(G, a1, b1, c1, d1, a2, b2, c2, d2, 1, 5, 0xf61e2562)

            
                MD5_STEP_X2(G, d1, a1, b1, c1, d2, a2, b2, c2, 6, 9, 0xc040b340)

            
                MD5_STEP_X2(G, c1, d1, a1, b1, c2, d2, a2, b2, 11, 14, 0x265e5a51)

            
                MD5_STEP_X2(G, b1, c1, d1, a1, b2, c2, d2, a2, 0, 20, 0xe9b6c7aa)

            
                MD5_STEP_X2(G, a1, b1, c1, d1, a2, b2, c2, d2, 5, 5, 0xd62f105d)

            
                MD5_STEP_X2(G, d1, a1, b1, c1, d2, a2, b2, c2, 10, 9, 0x02441453)

            
                MD5_STEP_X2(G, c1, d1, a1, b1, c2, d2, a2, b2, 15, 14, 0xd8a1e681)

            
                MD5_STEP_X2(G, b1, c1, d1, a1, b2, c2, d2, a2, 4, 20, 0xe7d3fbc8)

            
                MD5_STEP_X2(G, a1, b1, c1, d1, a2, b2, c2, d2, 9, 5, 0x21e1cde6)

            
                MD5_STEP_X2(G, d1, a1, b1, c1, d2, a2, b2, c2, 14, 9, 0xc33707d6)

            
                MD5_STEP_X2(G, c1, d1, a1, b1, c2, d2, a2, b2, 3, 14, 0xf4d50d87)

            
                MD5_STEP_X2(G, b1, c1, d1, a1, b2, c2, d2, a2, 8, 20, 0x455a14ed)

            
                MD5_STEP_X2(G, a1, b1, c1, d1, a2, b2, c2, d2, 13, 5, 0xa9e3e905)

            
                MD5_STEP_X2(G, d1, a1, b1, c1, d2, a2, b2, c2, 2, 9, 0xfcefa3f8)

            
                MD5_STEP_X2(G, c1, d1, a1, b1, c2, d2, a2, b2, 7, 14, 0x676f02d9)

            
                MD5_STEP_X2(G, b1, c1, d1, a1, b2, c2, d2, a2, 12, 20, 0x8d2a4c8a)


                MD5_STEP_X2(H, a1, b1, c1, d1, a2, b2, c2, d2, 5, 4, 0xfffa3942)

            
                MD5_STEP_X2(H, d1, a1, b1, c1, d2, a2, b2, c2, 8, 11, 0x8771f681)

            
                MD5_STEP_X2(H, c1, d1, a1, b1, c2, d2, a2, b2, 11, 16, 0x6d9d6122)

            
                MD5_STEP_X2(H, b1, c1, d1, a1, b2, c2, d2, a2, 14, 23, 0xfde5380c)

            
                MD5_STEP_X2(H, a1, b1, c1, d1, a2, b2, c2, d2, 1, 4, 0xa4beea44)

            
                MD5_STEP_X2(H, d1, a1, b1, c1, d2, a2, b2, c2, 4, 11, 0x4bdecfa9)

            
                MD5_STEP_X2(H, c1, d1, a1, b1, c2, d2, a2, b2, 7, 16, 0xf6bb4b60)

            
                MD5_STEP_X2(H, b1, c1, d1, a1, b2, c2, d2, a2, 10, 23, 0xbebfbc70)

            
                MD5_STEP_X2(H, a1, b1, c1, d1, a2, b2, c2, d2, 13, 4, 0x289b7ec6)

            
                MD5_STEP_X2(H, d1, a1, b1, c1, d2, a2, b2, c2, 0, 11, 0xeaa127fa)

            
                MD5_STEP_X2(H, c1, d1, a1, b1, c2, d2, a2, b2, 3, 16, 0xd4ef3085)

            
                MD5_STEP_X2(H, b1, c1, d1, a1, b2, c2, d2, a2, 6, 23, 0x04881d05)

            
                MD5_STEP_X2(H, a1, b1, c1, d1, a2, b2, c2, d2, 9, 4, 0xd9d4d039)

            
                MD5_STEP_X2(H, d1, a1, b1, c1, d2, a2, b2, c2, 12, 11, 0xe6db99e5)

            
                MD5_STEP_X2(H, c1, d1, a1, b1, c2, d2, a2, b2, 15, 16, 0x1fa27cf8)

            
                MD5_STEP_X2(H, b1, c1, d1, a1, b2, c2, d2, a2, 2, 23, 0xc4ac5665)


                MD5_STEP_X2(I, a1, b1, c1, d1, a2, b2, c2, d2, 0, 6, 0xf4292244)

            
                MD5_STEP_X2(I, d1, a1, b1, c1, d2, a2, b2, c2, 7, 10, 0x432aff97)

            
                MD5_STEP_X2(I, c1, d1, a1, b1, c2, d2, a2, b2, 14, 15, 0xab9423a7)

            
                MD5_STEP_X2(I, b1, c1, d1, a1, b2, c2, d2, a2, 5, 21, 0xfc93a039)

            
                MD5_STEP_X2(I, a1, b1, c1, d1, a2, b2, c2, d2, 12, 6, 0x655b59c3)

            
                MD5_STEP_X2(I, d1, a1, b1, c1, d2, a2, b2, c2, 3, 10, 0x8f0ccc92)

            
                MD5_STEP_X2(I, c1, d1, a1, b1, c2, d2, a2, b2, 10, 15, 0xffeff47d)

            
                MD5_STEP_X2(I, b1, c1, d1, a1, b2, c2, d2, a2, 1, 21, 0x85845dd1)

            
                MD5_STEP_X2(I, a1, b1, c1, d1, a2, b2, c2, d2, 8, 6, 0x6fa87e4f)

            
                MD5_STEP_X2(I, d1, a1, b1, c1, d2, a2, b2, c2, 15, 10, 0xfe2ce6e0)

            
                MD5_STEP_X2(I, c1, d1, a1, b1, c2, d2, a2, b2, 6, 15, 0xa3014314)

            
                MD5_STEP_X2(I, b1, c1, d1, a1, b2, c2, d2, a2, 13, 21, 0x4e0811a1)

            
                MD5_STEP_X2(I, a1, b1, c1, d1, a2, b2, c2, d2, 4, 6, 0xf7537e82)

            
                MD5_STEP_X2(I, d1, a1, b1, c1, d2, a2, b2, c2, 11, 10, 0xbd3af235)

            
                MD5_STEP_X2(I, c1, d1, a1, b1, c2, d2, a2, b2, 2, 15, 0x2ad7d2bb)

            
                MD5_STEP_X2(I, b1, c1, d1, a1, b2, c2, d2, a2, 9, 21, 0xeb86d391)


                return {Ops::add(a1, aa1), Ops::add(b1, bb1), Ops::add(c1, cc1), Ops::add(d1, dd1),

            
                        Ops::add(a2, aa2), Ops::add(b2, bb2), Ops::add(c2, cc2), Ops::add(d2, dd2)};

            
            }


            #undef MD5_STEP_X2


            template <typename Ops>

            
            uint32_t extract_lane(typename Ops::Vec v, size_t lane) {

            
                alignas(32) uint32_t values[Ops::LANES];

            
                Ops::storeu(values, v);

            
                return values[lane];

            
            }


            template <typename Ops>

            
            void md5_multi_buffer_compute(const unsigned char* const inputs[], const size_t lengths[],

            
                                          unsigned char* outputs, size_t count) {

            
                constexpr size_t N = Ops::LANES;

            
                using Vec = typename Ops::Vec;

            
                size_t count1 = std::min(count, N);

            
                size_t count2 = count > N ? count - N : 0;


                size_t num_blocks[2 * N];

            
                size_t max_blocks = 0;

            
                for (size_t i = 0; i < count; ++i) {

            
                    num_blocks[i] = md5_num_blocks(lengths[i]);

            
                    max_blocks = std::max(max_blocks, num_blocks[i]);

            
                }

            
                for (size_t i = count; i < 2 * N; ++i) {

            
                    num_blocks[i] = 1;

            
                }


                alignas(32) unsigned char final_buf[2 * N][128];

            
                size_t final_block_start[2 * N];

            
                size_t final_block_count[2 * N];

            
                for (size_t i = 0; i < count; ++i) {

            
                    final_block_start[i] = lengths[i] / 64;

            
                    final_block_count[i] = md5_pad_final_blocks(inputs[i], lengths[i], final_buf[i]);

            
                }

            
                for (size_t i = count; i < 2 * N; ++i) {

            
                    final_block_start[i] = 0;

            
                    final_block_count[i] = md5_pad_final_blocks(&MD5_DUMMY_INPUT, 0, final_buf[i]);

            
                }


                Vec a1 = Ops::set1(MD5_A0);

            
                Vec b1 = Ops::set1(MD5_B0);

            
                Vec c1 = Ops::set1(MD5_C0);

            
                Vec d1 = Ops::set1(MD5_D0);

            
                Vec a2 = Ops::set1(MD5_A0);

            
                Vec b2 = Ops::set1(MD5_B0);

            
                Vec c2 = Ops::set1(MD5_C0);

            
                Vec d2 = Ops::set1(MD5_D0);


                for (size_t block = 0; block < max_blocks; ++block) {

            
                    const unsigned char* block_ptrs[2 * N];

            
                    for (size_t i = 0; i < 2 * N; ++i) {

            
                        if (block < final_block_start[i]) {

            
                            block_ptrs[i] = inputs[i] + block * 64;

            
                        } else {

            
                            size_t final_index = block - final_block_start[i];

            
                            block_ptrs[i] = final_index < final_block_count[i] ? final_buf[i] + final_index * 64

            
                                                                               : final_buf[i];

            
                        }

            
                    }


                    Vec msg1[16];

            
                    Vec msg2[16];

            
                    Ops::gather_all_message_words(block_ptrs, msg1);

            
                    Ops::gather_all_message_words(block_ptrs + N, msg2);


                    auto st = md5_multi_buffer_block_x2<Ops>(a1, b1, c1, d1, a2, b2, c2, d2, msg1, msg2);

            
                    a1 = st.a1;

            
                    b1 = st.b1;

            
                    c1 = st.c1;

            
                    d1 = st.d1;

            
                    a2 = st.a2;

            
                    b2 = st.b2;

            
                    c2 = st.c2;

            
                    d2 = st.d2;


                    for (size_t lane = 0; lane < count1; ++lane) {

            
                        if (block + 1 == num_blocks[lane]) {

            
                            unsigned char* out = outputs + lane * MD5_DIGEST_LENGTH;

            
                            LittleEndian::Store32(out, extract_lane<Ops>(a1, lane));

            
                            LittleEndian::Store32(out + 4, extract_lane<Ops>(b1, lane));

            
                            LittleEndian::Store32(out + 8, extract_lane<Ops>(c1, lane));

            
                            LittleEndian::Store32(out + 12, extract_lane<Ops>(d1, lane));

            
                        }

            
                    }

            
                    for (size_t lane = 0; lane < count2; ++lane) {

            
                        if (block + 1 == num_blocks[N + lane]) {

            
                            unsigned char* out = outputs + (N + lane) * MD5_DIGEST_LENGTH;

            
                            LittleEndian::Store32(out, extract_lane<Ops>(a2, lane));

            
                            LittleEndian::Store32(out + 4, extract_lane<Ops>(b2, lane));

            
                            LittleEndian::Store32(out + 8, extract_lane<Ops>(c2, lane));

            
                            LittleEndian::Store32(out + 12, extract_lane<Ops>(d2, lane));

            
                        }

            
                    }

            
                }

            
            }


            void md5_binary_batch_avx2(const unsigned char* const inputs[], const size_t lengths[],

            
                                       unsigned char* outputs, size_t count) {

            
                constexpr size_t BATCH = 2 * AVX2MD5Ops::LANES;

            
                for (size_t base = 0; base < count; base += BATCH) {

            
                    size_t batch = std::min(BATCH, count - base);

            
                    const unsigned char* batch_inputs[BATCH];

            
                    size_t batch_lengths[BATCH];

            
                    for (size_t i = 0; i < batch; ++i) {

            
                        batch_inputs[i] = lengths[base + i] == 0 ? &MD5_DUMMY_INPUT : inputs[base + i];

            
                        batch_lengths[i] = lengths[base + i];

            
                    }

            
                    for (size_t i = batch; i < BATCH; ++i) {

            
                        batch_inputs[i] = &MD5_DUMMY_INPUT;

            
                        batch_lengths[i] = 0;

            
                    }

            
                    md5_multi_buffer_compute<AVX2MD5Ops>(batch_inputs, batch_lengths,

            
                                                         outputs + base * MD5_DIGEST_LENGTH, batch);

            
                }

            
            }


            #endif


            } // namespace


            Md5Digest::Md5Digest() {

            
                MD5_Init(&_md5_ctx);

            
            }


            void Md5Digest::update(const void* data, size_t length) {

            
                MD5_Update(&_md5_ctx, data, length);

            
            }


            void Md5Digest::digest() {

            
                unsigned char buf[MD5_DIGEST_LENGTH];

            
                MD5_Final(buf, &_md5_ctx);


                char hex_buf[MD5_HEX_LENGTH];

            
                md5_to_hex(buf, hex_buf);

            
                _hex.assign(hex_buf, MD5_HEX_LENGTH);

            
            }


            void md5_hex_batch(const unsigned char* const inputs[], const size_t lengths[], char* outputs,

            
                               size_t count) {

            
                if (count == 0) {

            
                    return;

            
                }


            #ifdef __AVX2__

            
                std::vector<unsigned char> digests(count * MD5_DIGEST_LENGTH);

            
                md5_binary_batch_avx2(inputs, lengths, digests.data(), count);

            
                for (size_t i = 0; i < count; ++i) {

            
                    md5_to_hex(digests.data() + i * MD5_DIGEST_LENGTH, outputs + i * MD5_HEX_LENGTH);

            
                }

            
            #else

            
                for (size_t i = 0; i < count; ++i) {

            
                    unsigned char digest[MD5_DIGEST_LENGTH];

            
                    MD5(lengths[i] == 0 ? &MD5_DUMMY_INPUT : inputs[i], lengths[i], digest);

            
                    md5_to_hex(digest, outputs + i * MD5_HEX_LENGTH);

            
                }

            
            #endif

            
            }


            } // namespace doris
	// Licensed to the Apache Software Foundation (ASF) under one
	// or more contributor license agreements. See the NOTICE file
	// distributed with this work for additional information
	// regarding copyright ownership. The ASF licenses this file
	// to you under the Apache License, Version 2.0 (the
	// "License"); you may not use this file except in compliance
	// with the License. You may obtain a copy of the License at
	//
	// http://www.apache.org/licenses/LICENSE-2.0
	//
	// Unless required by applicable law or agreed to in writing,
	// software distributed under the License is distributed on an
	// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
	// KIND, either express or implied. See the License for the
	// specific language governing permissions and limitations
	// under the License.

	#include "util/md5.h"

	#include <algorithm>
	#include <cstring>
	#include <vector>

	#ifdef __AVX2__
	#include <immintrin.h>
	#endif

	#include "exec/common/endian.h"

	namespace doris {

	namespace {

	constexpr unsigned char MD5_DUMMY_INPUT = 0;

	void md5_to_hex(const unsigned char* digest, char* out) {
	static constexpr char DIGITS[] = "0123456789abcdef";
	for (int i = 0; i < MD5_DIGEST_LENGTH; ++i) {
	*out++ = DIGITS[digest[i] >> 4];
	*out++ = DIGITS[digest[i] & 0x0F];
	}
	}

	#ifdef __AVX2__

	constexpr uint32_t MD5_A0 = 0x67452301;
	constexpr uint32_t MD5_B0 = 0xefcdab89;
	constexpr uint32_t MD5_C0 = 0x98badcfe;
	constexpr uint32_t MD5_D0 = 0x10325476;

	size_t md5_num_blocks(size_t len) {
	return (len + 9 + 63) / 64;
	}

	size_t md5_pad_final_blocks(const unsigned char* data, size_t len, unsigned char* out) {
	size_t full_blocks = len / 64;
	size_t tail = len % 64;
	size_t num_blocks = md5_num_blocks(len);
	size_t final_count = num_blocks - full_blocks;

	std::memset(out, 0, final_count * 64);
	std::memcpy(out, data + full_blocks * 64, tail);
	out[tail] = 0x80;
	LittleEndian::Store64(out + final_count * 64 - 8, static_cast<uint64_t>(len) * 8);

	return final_count;
	}

	struct AVX2MD5Ops {
	using Vec = __m256i;
	static constexpr size_t LANES = 8;

	static Vec add(Vec a, Vec b) { return _mm256_add_epi32(a, b); }

	static Vec set1(uint32_t v) { return _mm256_set1_epi32(static_cast<int>(v)); }

	static Vec loadu(const void* p) {
	return _mm256_loadu_si256(reinterpret_cast<const __m256i*>(p));
	}

	static void storeu(void* p, Vec v) { _mm256_storeu_si256(reinterpret_cast<__m256i*>(p), v); }

	template <int N>
	static Vec rotl(Vec x) {
	return _mm256_or_si256(_mm256_slli_epi32(x, N), _mm256_srli_epi32(x, 32 - N));
	}

	static Vec F(Vec b, Vec c, Vec d) {
	return _mm256_xor_si256(d, _mm256_and_si256(b, _mm256_xor_si256(c, d)));
	}

	static Vec G(Vec b, Vec c, Vec d) {
	return _mm256_xor_si256(c, _mm256_and_si256(d, _mm256_xor_si256(b, c)));
	}

	static Vec H(Vec b, Vec c, Vec d) { return _mm256_xor_si256(b, _mm256_xor_si256(c, d)); }

	static Vec I(Vec b, Vec c, Vec d) {
	return _mm256_xor_si256(c, _mm256_or_si256(b, _mm256_xor_si256(d, _mm256_set1_epi32(-1))));
	}

	static void gather_all_message_words(const unsigned char* const block_ptrs[], Vec msg[16]) {
	for (int half = 0; half < 2; ++half) {
	size_t off = half * 32;
	Vec r0 = loadu(block_ptrs[0] + off);
	Vec r1 = loadu(block_ptrs[1] + off);
	Vec r2 = loadu(block_ptrs[2] + off);
	Vec r3 = loadu(block_ptrs[3] + off);
	Vec r4 = loadu(block_ptrs[4] + off);
	Vec r5 = loadu(block_ptrs[5] + off);
	Vec r6 = loadu(block_ptrs[6] + off);
	Vec r7 = loadu(block_ptrs[7] + off);

	Vec t0 = _mm256_unpacklo_epi32(r0, r1);
	Vec t1 = _mm256_unpackhi_epi32(r0, r1);
	Vec t2 = _mm256_unpacklo_epi32(r2, r3);
	Vec t3 = _mm256_unpackhi_epi32(r2, r3);
	Vec t4 = _mm256_unpacklo_epi32(r4, r5);
	Vec t5 = _mm256_unpackhi_epi32(r4, r5);
	Vec t6 = _mm256_unpacklo_epi32(r6, r7);
	Vec t7 = _mm256_unpackhi_epi32(r6, r7);

	Vec u0 = _mm256_unpacklo_epi64(t0, t2);
	Vec u1 = _mm256_unpackhi_epi64(t0, t2);
	Vec u2 = _mm256_unpacklo_epi64(t1, t3);
	Vec u3 = _mm256_unpackhi_epi64(t1, t3);
	Vec u4 = _mm256_unpacklo_epi64(t4, t6);
	Vec u5 = _mm256_unpackhi_epi64(t4, t6);
	Vec u6 = _mm256_unpacklo_epi64(t5, t7);
	Vec u7 = _mm256_unpackhi_epi64(t5, t7);

	size_t base = half * 8;
	msg[base + 0] = _mm256_permute2x128_si256(u0, u4, 0x20);
	msg[base + 4] = _mm256_permute2x128_si256(u0, u4, 0x31);
	msg[base + 1] = _mm256_permute2x128_si256(u1, u5, 0x20);
	msg[base + 5] = _mm256_permute2x128_si256(u1, u5, 0x31);
	msg[base + 2] = _mm256_permute2x128_si256(u2, u6, 0x20);
	msg[base + 6] = _mm256_permute2x128_si256(u2, u6, 0x31);
	msg[base + 3] = _mm256_permute2x128_si256(u3, u7, 0x20);
	msg[base + 7] = _mm256_permute2x128_si256(u3, u7, 0x31);
	}
	}
	};

	#define MD5_STEP_X2(func, w1, x1, y1, z1, w2, x2, y2, z2, g, s, ti) \
	{ \
	Vec t1 = Ops::func(x1, y1, z1); \
	Vec t2 = Ops::func(x2, y2, z2); \
	t1 = Ops::add(t1, w1); \
	t2 = Ops::add(t2, w2); \
	Vec k = Ops::set1(ti); \
	t1 = Ops::add(t1, k); \
	t2 = Ops::add(t2, k); \
	t1 = Ops::add(t1, msg1[g]); \
	t2 = Ops::add(t2, msg2[g]); \
	(w1) = Ops::add(x1, Ops::template rotl<s>(t1)); \
	(w2) = Ops::add(x2, Ops::template rotl<s>(t2)); \
	}

	template <typename Ops>
	struct MD5X2State {
	typename Ops::Vec a1, b1, c1, d1, a2, b2, c2, d2;
	};

	template <typename Ops>
	MD5X2State<Ops> md5_multi_buffer_block_x2(typename Ops::Vec a1, typename Ops::Vec b1,
	typename Ops::Vec c1, typename Ops::Vec d1,
	typename Ops::Vec a2, typename Ops::Vec b2,
	typename Ops::Vec c2, typename Ops::Vec d2,
	const typename Ops::Vec msg1[16],
	const typename Ops::Vec msg2[16]) {
	using Vec = typename Ops::Vec;
	Vec aa1 = a1;
	Vec bb1 = b1;
	Vec cc1 = c1;
	Vec dd1 = d1;
	Vec aa2 = a2;
	Vec bb2 = b2;
	Vec cc2 = c2;
	Vec dd2 = d2;

	MD5_STEP_X2(F, a1, b1, c1, d1, a2, b2, c2, d2, 0, 7, 0xd76aa478)
	MD5_STEP_X2(F, d1, a1, b1, c1, d2, a2, b2, c2, 1, 12, 0xe8c7b756)
	MD5_STEP_X2(F, c1, d1, a1, b1, c2, d2, a2, b2, 2, 17, 0x242070db)
	MD5_STEP_X2(F, b1, c1, d1, a1, b2, c2, d2, a2, 3, 22, 0xc1bdceee)
	MD5_STEP_X2(F, a1, b1, c1, d1, a2, b2, c2, d2, 4, 7, 0xf57c0faf)
	MD5_STEP_X2(F, d1, a1, b1, c1, d2, a2, b2, c2, 5, 12, 0x4787c62a)
	MD5_STEP_X2(F, c1, d1, a1, b1, c2, d2, a2, b2, 6, 17, 0xa8304613)
	MD5_STEP_X2(F, b1, c1, d1, a1, b2, c2, d2, a2, 7, 22, 0xfd469501)
	MD5_STEP_X2(F, a1, b1, c1, d1, a2, b2, c2, d2, 8, 7, 0x698098d8)
	MD5_STEP_X2(F, d1, a1, b1, c1, d2, a2, b2, c2, 9, 12, 0x8b44f7af)
	MD5_STEP_X2(F, c1, d1, a1, b1, c2, d2, a2, b2, 10, 17, 0xffff5bb1)
	MD5_STEP_X2(F, b1, c1, d1, a1, b2, c2, d2, a2, 11, 22, 0x895cd7be)
	MD5_STEP_X2(F, a1, b1, c1, d1, a2, b2, c2, d2, 12, 7, 0x6b901122)
	MD5_STEP_X2(F, d1, a1, b1, c1, d2, a2, b2, c2, 13, 12, 0xfd987193)
	MD5_STEP_X2(F, c1, d1, a1, b1, c2, d2, a2, b2, 14, 17, 0xa679438e)
	MD5_STEP_X2(F, b1, c1, d1, a1, b2, c2, d2, a2, 15, 22, 0x49b40821)

	MD5_STEP_X2(G, a1, b1, c1, d1, a2, b2, c2, d2, 1, 5, 0xf61e2562)
	MD5_STEP_X2(G, d1, a1, b1, c1, d2, a2, b2, c2, 6, 9, 0xc040b340)
	MD5_STEP_X2(G, c1, d1, a1, b1, c2, d2, a2, b2, 11, 14, 0x265e5a51)
	MD5_STEP_X2(G, b1, c1, d1, a1, b2, c2, d2, a2, 0, 20, 0xe9b6c7aa)
	MD5_STEP_X2(G, a1, b1, c1, d1, a2, b2, c2, d2, 5, 5, 0xd62f105d)
	MD5_STEP_X2(G, d1, a1, b1, c1, d2, a2, b2, c2, 10, 9, 0x02441453)
	MD5_STEP_X2(G, c1, d1, a1, b1, c2, d2, a2, b2, 15, 14, 0xd8a1e681)
	MD5_STEP_X2(G, b1, c1, d1, a1, b2, c2, d2, a2, 4, 20, 0xe7d3fbc8)
	MD5_STEP_X2(G, a1, b1, c1, d1, a2, b2, c2, d2, 9, 5, 0x21e1cde6)
	MD5_STEP_X2(G, d1, a1, b1, c1, d2, a2, b2, c2, 14, 9, 0xc33707d6)
	MD5_STEP_X2(G, c1, d1, a1, b1, c2, d2, a2, b2, 3, 14, 0xf4d50d87)
	MD5_STEP_X2(G, b1, c1, d1, a1, b2, c2, d2, a2, 8, 20, 0x455a14ed)
	MD5_STEP_X2(G, a1, b1, c1, d1, a2, b2, c2, d2, 13, 5, 0xa9e3e905)
	MD5_STEP_X2(G, d1, a1, b1, c1, d2, a2, b2, c2, 2, 9, 0xfcefa3f8)
	MD5_STEP_X2(G, c1, d1, a1, b1, c2, d2, a2, b2, 7, 14, 0x676f02d9)
	MD5_STEP_X2(G, b1, c1, d1, a1, b2, c2, d2, a2, 12, 20, 0x8d2a4c8a)

	MD5_STEP_X2(H, a1, b1, c1, d1, a2, b2, c2, d2, 5, 4, 0xfffa3942)
	MD5_STEP_X2(H, d1, a1, b1, c1, d2, a2, b2, c2, 8, 11, 0x8771f681)
	MD5_STEP_X2(H, c1, d1, a1, b1, c2, d2, a2, b2, 11, 16, 0x6d9d6122)
	MD5_STEP_X2(H, b1, c1, d1, a1, b2, c2, d2, a2, 14, 23, 0xfde5380c)
	MD5_STEP_X2(H, a1, b1, c1, d1, a2, b2, c2, d2, 1, 4, 0xa4beea44)
	MD5_STEP_X2(H, d1, a1, b1, c1, d2, a2, b2, c2, 4, 11, 0x4bdecfa9)
	MD5_STEP_X2(H, c1, d1, a1, b1, c2, d2, a2, b2, 7, 16, 0xf6bb4b60)
	MD5_STEP_X2(H, b1, c1, d1, a1, b2, c2, d2, a2, 10, 23, 0xbebfbc70)
	MD5_STEP_X2(H, a1, b1, c1, d1, a2, b2, c2, d2, 13, 4, 0x289b7ec6)
	MD5_STEP_X2(H, d1, a1, b1, c1, d2, a2, b2, c2, 0, 11, 0xeaa127fa)
	MD5_STEP_X2(H, c1, d1, a1, b1, c2, d2, a2, b2, 3, 16, 0xd4ef3085)
	MD5_STEP_X2(H, b1, c1, d1, a1, b2, c2, d2, a2, 6, 23, 0x04881d05)
	MD5_STEP_X2(H, a1, b1, c1, d1, a2, b2, c2, d2, 9, 4, 0xd9d4d039)
	MD5_STEP_X2(H, d1, a1, b1, c1, d2, a2, b2, c2, 12, 11, 0xe6db99e5)
	MD5_STEP_X2(H, c1, d1, a1, b1, c2, d2, a2, b2, 15, 16, 0x1fa27cf8)
	MD5_STEP_X2(H, b1, c1, d1, a1, b2, c2, d2, a2, 2, 23, 0xc4ac5665)

	MD5_STEP_X2(I, a1, b1, c1, d1, a2, b2, c2, d2, 0, 6, 0xf4292244)
	MD5_STEP_X2(I, d1, a1, b1, c1, d2, a2, b2, c2, 7, 10, 0x432aff97)
	MD5_STEP_X2(I, c1, d1, a1, b1, c2, d2, a2, b2, 14, 15, 0xab9423a7)
	MD5_STEP_X2(I, b1, c1, d1, a1, b2, c2, d2, a2, 5, 21, 0xfc93a039)
	MD5_STEP_X2(I, a1, b1, c1, d1, a2, b2, c2, d2, 12, 6, 0x655b59c3)
	MD5_STEP_X2(I, d1, a1, b1, c1, d2, a2, b2, c2, 3, 10, 0x8f0ccc92)
	MD5_STEP_X2(I, c1, d1, a1, b1, c2, d2, a2, b2, 10, 15, 0xffeff47d)
	MD5_STEP_X2(I, b1, c1, d1, a1, b2, c2, d2, a2, 1, 21, 0x85845dd1)
	MD5_STEP_X2(I, a1, b1, c1, d1, a2, b2, c2, d2, 8, 6, 0x6fa87e4f)
	MD5_STEP_X2(I, d1, a1, b1, c1, d2, a2, b2, c2, 15, 10, 0xfe2ce6e0)
	MD5_STEP_X2(I, c1, d1, a1, b1, c2, d2, a2, b2, 6, 15, 0xa3014314)
	MD5_STEP_X2(I, b1, c1, d1, a1, b2, c2, d2, a2, 13, 21, 0x4e0811a1)
	MD5_STEP_X2(I, a1, b1, c1, d1, a2, b2, c2, d2, 4, 6, 0xf7537e82)
	MD5_STEP_X2(I, d1, a1, b1, c1, d2, a2, b2, c2, 11, 10, 0xbd3af235)
	MD5_STEP_X2(I, c1, d1, a1, b1, c2, d2, a2, b2, 2, 15, 0x2ad7d2bb)
	MD5_STEP_X2(I, b1, c1, d1, a1, b2, c2, d2, a2, 9, 21, 0xeb86d391)

	return {Ops::add(a1, aa1), Ops::add(b1, bb1), Ops::add(c1, cc1), Ops::add(d1, dd1),
	Ops::add(a2, aa2), Ops::add(b2, bb2), Ops::add(c2, cc2), Ops::add(d2, dd2)};
	}

	#undef MD5_STEP_X2

	template <typename Ops>
	uint32_t extract_lane(typename Ops::Vec v, size_t lane) {
	alignas(32) uint32_t values[Ops::LANES];
	Ops::storeu(values, v);
	return values[lane];
	}

	template <typename Ops>
	void md5_multi_buffer_compute(const unsigned char* const inputs[], const size_t lengths[],
	unsigned char* outputs, size_t count) {
	constexpr size_t N = Ops::LANES;
	using Vec = typename Ops::Vec;
	size_t count1 = std::min(count, N);
	size_t count2 = count > N ? count - N : 0;

	size_t num_blocks[2 * N];
	size_t max_blocks = 0;
	for (size_t i = 0; i < count; ++i) {
	num_blocks[i] = md5_num_blocks(lengths[i]);
	max_blocks = std::max(max_blocks, num_blocks[i]);
	}
	for (size_t i = count; i < 2 * N; ++i) {
	num_blocks[i] = 1;
	}

	alignas(32) unsigned char final_buf[2 * N][128];
	size_t final_block_start[2 * N];
	size_t final_block_count[2 * N];
	for (size_t i = 0; i < count; ++i) {
	final_block_start[i] = lengths[i] / 64;
	final_block_count[i] = md5_pad_final_blocks(inputs[i], lengths[i], final_buf[i]);
	}
	for (size_t i = count; i < 2 * N; ++i) {
	final_block_start[i] = 0;
	final_block_count[i] = md5_pad_final_blocks(&MD5_DUMMY_INPUT, 0, final_buf[i]);
	}

	Vec a1 = Ops::set1(MD5_A0);
	Vec b1 = Ops::set1(MD5_B0);
	Vec c1 = Ops::set1(MD5_C0);
	Vec d1 = Ops::set1(MD5_D0);
	Vec a2 = Ops::set1(MD5_A0);
	Vec b2 = Ops::set1(MD5_B0);
	Vec c2 = Ops::set1(MD5_C0);
	Vec d2 = Ops::set1(MD5_D0);

	for (size_t block = 0; block < max_blocks; ++block) {
	const unsigned char* block_ptrs[2 * N];
	for (size_t i = 0; i < 2 * N; ++i) {
	if (block < final_block_start[i]) {
	block_ptrs[i] = inputs[i] + block * 64;
	} else {
	size_t final_index = block - final_block_start[i];
	block_ptrs[i] = final_index < final_block_count[i] ? final_buf[i] + final_index * 64
	: final_buf[i];
	}
	}

	Vec msg1[16];
	Vec msg2[16];
	Ops::gather_all_message_words(block_ptrs, msg1);
	Ops::gather_all_message_words(block_ptrs + N, msg2);

	auto st = md5_multi_buffer_block_x2<Ops>(a1, b1, c1, d1, a2, b2, c2, d2, msg1, msg2);
	a1 = st.a1;
	b1 = st.b1;
	c1 = st.c1;
	d1 = st.d1;
	a2 = st.a2;
	b2 = st.b2;
	c2 = st.c2;
	d2 = st.d2;

	for (size_t lane = 0; lane < count1; ++lane) {
	if (block + 1 == num_blocks[lane]) {
	unsigned char* out = outputs + lane * MD5_DIGEST_LENGTH;
	LittleEndian::Store32(out, extract_lane<Ops>(a1, lane));
	LittleEndian::Store32(out + 4, extract_lane<Ops>(b1, lane));
	LittleEndian::Store32(out + 8, extract_lane<Ops>(c1, lane));
	LittleEndian::Store32(out + 12, extract_lane<Ops>(d1, lane));
	}
	}
	for (size_t lane = 0; lane < count2; ++lane) {
	if (block + 1 == num_blocks[N + lane]) {
	unsigned char* out = outputs + (N + lane) * MD5_DIGEST_LENGTH;
	LittleEndian::Store32(out, extract_lane<Ops>(a2, lane));
	LittleEndian::Store32(out + 4, extract_lane<Ops>(b2, lane));
	LittleEndian::Store32(out + 8, extract_lane<Ops>(c2, lane));
	LittleEndian::Store32(out + 12, extract_lane<Ops>(d2, lane));
	}
	}
	}
	}

	void md5_binary_batch_avx2(const unsigned char* const inputs[], const size_t lengths[],
	unsigned char* outputs, size_t count) {
	constexpr size_t BATCH = 2 * AVX2MD5Ops::LANES;
	for (size_t base = 0; base < count; base += BATCH) {
	size_t batch = std::min(BATCH, count - base);
	const unsigned char* batch_inputs[BATCH];
	size_t batch_lengths[BATCH];
	for (size_t i = 0; i < batch; ++i) {
	batch_inputs[i] = lengths[base + i] == 0 ? &MD5_DUMMY_INPUT : inputs[base + i];
	batch_lengths[i] = lengths[base + i];
	}
	for (size_t i = batch; i < BATCH; ++i) {
	batch_inputs[i] = &MD5_DUMMY_INPUT;
	batch_lengths[i] = 0;
	}
	md5_multi_buffer_compute<AVX2MD5Ops>(batch_inputs, batch_lengths,
	outputs + base * MD5_DIGEST_LENGTH, batch);
	}
	}

	#endif

	} // namespace

	Md5Digest::Md5Digest() {
	MD5_Init(&_md5_ctx);
	}

	void Md5Digest::update(const void* data, size_t length) {
	MD5_Update(&_md5_ctx, data, length);
	}

	void Md5Digest::digest() {
	unsigned char buf[MD5_DIGEST_LENGTH];
	MD5_Final(buf, &_md5_ctx);

	char hex_buf[MD5_HEX_LENGTH];
	md5_to_hex(buf, hex_buf);
	_hex.assign(hex_buf, MD5_HEX_LENGTH);
	}

	void md5_hex_batch(const unsigned char* const inputs[], const size_t lengths[], char* outputs,
	size_t count) {
	if (count == 0) {
	return;
	}

	#ifdef __AVX2__
	std::vector<unsigned char> digests(count * MD5_DIGEST_LENGTH);
	md5_binary_batch_avx2(inputs, lengths, digests.data(), count);
	for (size_t i = 0; i < count; ++i) {
	md5_to_hex(digests.data() + i * MD5_DIGEST_LENGTH, outputs + i * MD5_HEX_LENGTH);
	}
	#else
	for (size_t i = 0; i < count; ++i) {
	unsigned char digest[MD5_DIGEST_LENGTH];
	MD5(lengths[i] == 0 ? &MD5_DUMMY_INPUT : inputs[i], lengths[i], digest);
	md5_to_hex(digest, outputs + i * MD5_HEX_LENGTH);
	}
	#endif
	}

	} // namespace doris