/*
* All or portions of this file Copyright (c) Amazon.com, Inc. or its affiliates or
* its licensors.
*
* For complete copyright and license terms please see the LICENSE at the root of this
* distribution (the "License"). All use of this software is governed by the License,
* or, if provided, by the license below or the license accompanying this file. Do not
* remove or modify any license notices. This file is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
*
*/
// Original file Copyright Crytek GMBH or its affiliates, used under license.

#ifndef CRYINCLUDE_CRYCOMMON_FINDZERORANGES_H
#define CRYINCLUDE_CRYCOMMON_FINDZERORANGES_H
#pragma once


template <typename Func>
inline void FindZeroRanges(const uint32* str, size_t strLen, Func& yield)
{
    size_t carry = 0;
    size_t bitIdx = 0;

    for (size_t wordIdx = 0; wordIdx < strLen; ++wordIdx)
    {
        size_t wordBitIdx = 0;
        int64 word = str[wordIdx];

        // Set up sign extension to insert bits that are the last bit, inverted.

        if (!(word & 0x80000000))
        {
            reinterpret_cast<uint64&>(word) |= 0xffffffff00000000ULL;
        }

        do
        {
            size_t wordZeroRunLen = countTrailingZeroes(word);

            wordBitIdx += wordZeroRunLen;
            carry += wordZeroRunLen;

            if (wordBitIdx == 32)
            {
                break;
            }

            yield(bitIdx, carry);
            word >>= wordZeroRunLen;
            bitIdx += carry;
            carry = 0;

            size_t wordOneRunLen = countTrailingZeroes(~word);
            bitIdx += wordOneRunLen;
            wordBitIdx += wordOneRunLen;

            if (wordBitIdx == 32)
            {
                break;
            }

            word >>= wordOneRunLen;
        }
        while (true);
    }

    if (carry)
    {
        yield(bitIdx, carry);
    }
}

#endif // CRYINCLUDE_CRYCOMMON_FINDZERORANGES_H