path: root/xfa/src/fxbarcode/qrcode/BC_QRFinderPatternFinder.cpp

// Copyright 2014 PDFium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

// Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com
// Original code is licensed as follows:
/*
 * Copyright 2007 ZXing authors
 *
 * Licensed 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 "../barcode.h"
#include "../BC_ResultPoint.h"
#include "../common/BC_CommonBitMatrix.h"
#include "BC_QRFinderPatternFinder.h"
#include "BC_FinderPatternInfo.h"
#include "BC_QRFinderPattern.h"
const FX_INT32 CBC_QRFinderPatternFinder::CENTER_QUORUM = 2;
const FX_INT32 CBC_QRFinderPatternFinder::MIN_SKIP = 3;
const FX_INT32 CBC_QRFinderPatternFinder::MAX_MODULES = 57;
const FX_INT32 CBC_QRFinderPatternFinder::INTEGER_MATH_SHIFT = 8;
CBC_QRFinderPatternFinder::CBC_QRFinderPatternFinder(CBC_CommonBitMatrix* image)
{
    m_image = image;
    m_crossCheckStateCount.SetSize(5);
    m_hasSkipped = FALSE;
}
CBC_QRFinderPatternFinder::~CBC_QRFinderPatternFinder()
{
    for(FX_INT32 i = 0; i < m_possibleCenters.GetSize(); i++) {
        delete (CBC_QRFinderPattern*)m_possibleCenters[i];
    }
    m_possibleCenters.RemoveAll();
}
class ClosestToAverageComparator
{
private:
    FX_FLOAT m_averageModuleSize;
public:
    ClosestToAverageComparator(FX_FLOAT averageModuleSize) : m_averageModuleSize(averageModuleSize)
    {
    }
    FX_INT32 operator()(FinderPattern *a, FinderPattern *b)
    {
        FX_FLOAT dA = (FX_FLOAT)fabs(a->GetEstimatedModuleSize() - m_averageModuleSize);
        FX_FLOAT dB = (FX_FLOAT)fabs(b->GetEstimatedModuleSize() - m_averageModuleSize);
        return dA < dB ? -1 : dA > dB ? 1 : 0;
    }
};
class CenterComparator
{
public:
    FX_INT32 operator()(FinderPattern *a, FinderPattern *b)
    {
        return b->GetCount() - a->GetCount();
    }
};
CBC_CommonBitMatrix *CBC_QRFinderPatternFinder::GetImage()
{
    return m_image;
}
CFX_Int32Array &CBC_QRFinderPatternFinder::GetCrossCheckStateCount()
{
    m_crossCheckStateCount[0] = 0;
    m_crossCheckStateCount[1] = 0;
    m_crossCheckStateCount[2] = 0;
    m_crossCheckStateCount[3] = 0;
    m_crossCheckStateCount[4] = 0;
    return m_crossCheckStateCount;
}
CFX_PtrArray *CBC_QRFinderPatternFinder::GetPossibleCenters()
{
    return &m_possibleCenters;
}
CBC_QRFinderPatternInfo* CBC_QRFinderPatternFinder::Find(FX_INT32 hint, FX_INT32 &e)
{
    FX_INT32 maxI = m_image->GetHeight();
    FX_INT32 maxJ = m_image->GetWidth();
    FX_INT32 iSkip = (3 * maxI) / (4 * MAX_MODULES);
    if(iSkip < MIN_SKIP || 0) {
        iSkip = MIN_SKIP;
    }
    FX_BOOL done = FALSE;
    CFX_Int32Array stateCount;
    stateCount.SetSize(5);
    for(FX_INT32 i = iSkip - 1; i < maxI && !done; i += iSkip) {
        stateCount[0] = 0;
        stateCount[1] = 0;
        stateCount[2] = 0;
        stateCount[3] = 0;
        stateCount[4] = 0;
        FX_INT32 currentState = 0;
        for(FX_INT32 j = 0; j < maxJ; j++) {
            if(m_image->Get(j, i)) {
                if((currentState & 1) == 1) {
                    currentState++;
                }
                stateCount[currentState]++;
            } else {
                if((currentState & 1) == 0) {
                    if(currentState == 4) {
                        if(FoundPatternCross(stateCount)) {
                            FX_BOOL confirmed = HandlePossibleCenter(stateCount, i, j);
                            if(confirmed) {
                                iSkip = 2;
                                if(m_hasSkipped) {
                                    done = HaveMultiplyConfirmedCenters();
                                } else {
                                    FX_INT32 rowSkip = FindRowSkip();
                                    if(rowSkip > stateCount[2]) {
                                        i += rowSkip - stateCount[2] - iSkip;
                                        j = maxJ - 1;
                                    }
                                }
                            } else {
                                do {
                                    j++;
                                } while (j < maxJ && !m_image->Get(j, i));
                                j--;
                            }
                            currentState = 0;
                            stateCount[0] = 0;
                            stateCount[1] = 0;
                            stateCount[2] = 0;
                            stateCount[3] = 0;
                            stateCount[4] = 0;
                        } else {
                            stateCount[0] = stateCount[2];
                            stateCount[1] = stateCount[3];
                            stateCount[2] = stateCount[4];
                            stateCount[3] = 1;
                            stateCount[4] = 0;
                            currentState = 3;
                        }
                    } else {
                        stateCount[++currentState]++;
                    }
                } else {
                    stateCount[currentState]++;
                }
            }
        }
        if(FoundPatternCross(stateCount)) {
            FX_BOOL confirmed = HandlePossibleCenter(stateCount, i, maxJ);
            if(confirmed) {
                iSkip = stateCount[0];
                if(m_hasSkipped) {
                    done = HaveMultiplyConfirmedCenters();
                }
            }
        }
    }
    CFX_PtrArray* ptr = SelectBestpatterns(e);
    BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
    CBC_AutoPtr<CFX_PtrArray > patternInfo(ptr);
    OrderBestPatterns(patternInfo.get());
    return new CBC_QRFinderPatternInfo(patternInfo.get());
}
void CBC_QRFinderPatternFinder::OrderBestPatterns(CFX_PtrArray *patterns)
{
    FX_FLOAT abDistance = Distance((CBC_ResultPoint*)(*patterns)[0], (CBC_ResultPoint*)(*patterns)[1]);
    FX_FLOAT bcDistance = Distance((CBC_ResultPoint*)(*patterns)[1], (CBC_ResultPoint*)(*patterns)[2]);
    FX_FLOAT acDistance = Distance((CBC_ResultPoint*)(*patterns)[0], (CBC_ResultPoint*)(*patterns)[2]);
    CBC_QRFinderPattern *topLeft, *topRight, *bottomLeft;
    if (bcDistance >= abDistance && bcDistance >= acDistance) {
        topLeft = (CBC_QRFinderPattern *)(*patterns)[0];
        topRight = (CBC_QRFinderPattern *)(*patterns)[1];
        bottomLeft = (CBC_QRFinderPattern *)(*patterns)[2];
    } else if (acDistance >= bcDistance && acDistance >= abDistance) {
        topLeft = (CBC_QRFinderPattern *)(*patterns)[1];
        topRight = (CBC_QRFinderPattern *)(*patterns)[0];
        bottomLeft = (CBC_QRFinderPattern *)(*patterns)[2];
    } else {
        topLeft = (CBC_QRFinderPattern *)(*patterns)[2];
        topRight = (CBC_QRFinderPattern *)(*patterns)[0];
        bottomLeft = (CBC_QRFinderPattern *)(*patterns)[1];
    }
    if ((bottomLeft->GetY() - topLeft->GetY()) * (topRight->GetX() - topLeft->GetX()) < (bottomLeft->GetX()
            - topLeft->GetX()) * (topRight->GetY() - topLeft->GetY())) {
        CBC_QRFinderPattern* temp = topRight;
        topRight = bottomLeft;
        bottomLeft = temp;
    }
    (*patterns)[0] = bottomLeft;
    (*patterns)[1] = topLeft;
    (*patterns)[2] = topRight;
}
FX_FLOAT CBC_QRFinderPatternFinder::Distance(CBC_ResultPoint* point1, CBC_ResultPoint* point2)
{
    FX_FLOAT dx = point1->GetX() - point2->GetX();
    FX_FLOAT dy = point1->GetY() - point2->GetY();
    return (FX_FLOAT)FXSYS_sqrt(dx * dx + dy * dy);
}
FX_FLOAT CBC_QRFinderPatternFinder::CenterFromEnd(const CFX_Int32Array &stateCount, FX_INT32 end)
{
    return (FX_FLOAT)(end - stateCount[4] - stateCount[3]) - stateCount[2] / 2.0f;
}
FX_BOOL CBC_QRFinderPatternFinder::FoundPatternCross(const CFX_Int32Array &stateCount)
{
    FX_INT32 totalModuleSize = 0;
    for (FX_INT32 i = 0; i < 5; i++) {
        FX_INT32 count = stateCount[i];
        if (count == 0) {
            return FALSE;
        }
        totalModuleSize += count;
    }
    if (totalModuleSize < 7) {
        return FALSE;
    }
    FX_INT32 moduleSize = (totalModuleSize << INTEGER_MATH_SHIFT) / 7;
    FX_INT32 maxVariance = moduleSize / 2;
    return FXSYS_abs(moduleSize - (stateCount[0] << INTEGER_MATH_SHIFT)) < maxVariance &&
           FXSYS_abs(moduleSize - (stateCount[1] << INTEGER_MATH_SHIFT)) < maxVariance &&
           FXSYS_abs(3 * moduleSize - (stateCount[2] << INTEGER_MATH_SHIFT)) < 3 * maxVariance &&
           FXSYS_abs(moduleSize - (stateCount[3] << INTEGER_MATH_SHIFT)) < maxVariance &&
           FXSYS_abs(moduleSize - (stateCount[4] << INTEGER_MATH_SHIFT)) < maxVariance;
}
FX_FLOAT CBC_QRFinderPatternFinder::CrossCheckVertical(FX_INT32 startI, FX_INT32 centerJ, FX_INT32 maxCount,
        FX_INT32 originalStateCountTotal)
{
    CBC_CommonBitMatrix *image = m_image;
    FX_INT32 maxI = image->GetHeight();
    CFX_Int32Array &stateCount = GetCrossCheckStateCount();
    FX_INT32 i = startI;
    while(i >= 0 && image->Get(centerJ, i)) {
        stateCount[2]++;
        i--;
    }
    if(i < 0) {
        return FXSYS_nan();
    }
    while(i >= 0 && !image->Get(centerJ, i) && stateCount[1] <= maxCount) {
        stateCount[1]++;
        i--;
    }
    if(i < 0 || stateCount[1] > maxCount) {
        return FXSYS_nan();
    }
    while(i >= 0 && image->Get(centerJ, i) && stateCount[0] <= maxCount) {
        stateCount[0]++;
        i--;
    }
    if(stateCount[0] > maxCount) {
        return FXSYS_nan();
    }
    i = startI + 1;
    while(i < maxI && image->Get(centerJ, i)) {
        stateCount[2]++;
        i++;
    }
    if(i == maxI) {
        return FXSYS_nan();
    }
    while (i < maxI && !image->Get(centerJ, i) && stateCount[3] < maxCount) {
        stateCount[3]++;
        i++;
    }
    if (i == maxI || stateCount[3] >= maxCount) {
        return FXSYS_nan();
    }
    while (i < maxI && image->Get(centerJ, i) && stateCount[4] < maxCount) {
        stateCount[4]++;
        i++;
    }
    if (stateCount[4] >= maxCount) {
        return FXSYS_nan();
    }
    FX_INT32 stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] + stateCount[3] + stateCount[4];
    if (5 * FXSYS_abs(stateCountTotal - originalStateCountTotal) >= originalStateCountTotal) {
        return FXSYS_nan();
    }
    return FoundPatternCross(stateCount) ? CenterFromEnd(stateCount, i) : FXSYS_nan();
}
FX_FLOAT CBC_QRFinderPatternFinder::CrossCheckHorizontal(FX_INT32 startJ, FX_INT32 centerI, FX_INT32 maxCount, FX_INT32 originalStateCountTotal)
{
    CBC_CommonBitMatrix *image = m_image;
    FX_INT32 maxJ = image->GetWidth();
    CFX_Int32Array &stateCount = GetCrossCheckStateCount();
    FX_INT32 j = startJ;
    while (j >= 0 && image->Get(j, centerI)) {
        stateCount[2]++;
        j--;
    }
    if (j < 0) {
        return FXSYS_nan();
    }
    while (j >= 0 && !image->Get(j, centerI) && stateCount[1] <= maxCount) {
        stateCount[1]++;
        j--;
    }
    if (j < 0 || stateCount[1] > maxCount) {
        return FXSYS_nan();
    }
    while (j >= 0 && image->Get(j, centerI) && stateCount[0] <= maxCount) {
        stateCount[0]++;
        j--;
    }
    if (stateCount[0] > maxCount) {
        return FXSYS_nan();
    }
    j = startJ + 1;
    while (j < maxJ && image->Get(j, centerI)) {
        stateCount[2]++;
        j++;
    }
    if (j == maxJ) {
        return FXSYS_nan();
    }
    while (j < maxJ && !image->Get(j, centerI) && stateCount[3] < maxCount) {
        stateCount[3]++;
        j++;
    }
    if (j == maxJ || stateCount[3] >= maxCount) {
        return FXSYS_nan();
    }
    while (j < maxJ && image->Get(j, centerI) && stateCount[4] < maxCount) {
        stateCount[4]++;
        j++;
    }
    if (stateCount[4] >= maxCount) {
        return FXSYS_nan();
    }
    FX_INT32 stateCountTotal = stateCount[0] + stateCount[1] +
                               stateCount[2] + stateCount[3] +
                               stateCount[4];
    if (5 * FXSYS_abs(stateCountTotal - originalStateCountTotal) >= originalStateCountTotal) {
        return FXSYS_nan();
    }
    return FoundPatternCross(stateCount) ? CenterFromEnd(stateCount, j) : FXSYS_nan();
}
FX_BOOL CBC_QRFinderPatternFinder::HandlePossibleCenter(const CFX_Int32Array &stateCount, FX_INT32 i, FX_INT32 j)
{
    FX_INT32 stateCountTotal = stateCount[0] + stateCount[1] + stateCount[2] + stateCount[3] + stateCount[4];
    FX_FLOAT centerJ = CenterFromEnd(stateCount, j);
    FX_FLOAT centerI = CrossCheckVertical(i, (FX_INT32) centerJ, stateCount[2], stateCountTotal);
    if(!FXSYS_isnan(centerI)) {
        centerJ = CrossCheckHorizontal((FX_INT32) centerJ, (FX_INT32) centerI, stateCount[2], stateCountTotal);
        if(!FXSYS_isnan(centerJ)) {
            FX_FLOAT estimatedModuleSize = (FX_FLOAT) stateCountTotal / 7.0f;
            FX_BOOL found = FALSE;
            FX_INT32 max = m_possibleCenters.GetSize();
            for(FX_INT32 index = 0; index < max; index++) {
                CBC_QRFinderPattern *center = (CBC_QRFinderPattern*)(m_possibleCenters[index]);
                if(center->AboutEquals(estimatedModuleSize, centerI, centerJ)) {
                    center->IncrementCount();
                    found = TRUE;
                    break;
                }
            }
            if(!found) {
                m_possibleCenters.Add(FX_NEW CBC_QRFinderPattern(centerJ, centerI, estimatedModuleSize));
            }
            return TRUE;
        }
    }
    return FALSE;
}
FX_INT32 CBC_QRFinderPatternFinder::FindRowSkip()
{
    FX_INT32 max = m_possibleCenters.GetSize();
    if (max <= 1) {
        return 0;
    }
    FinderPattern *firstConfirmedCenter = NULL;
    for (FX_INT32 i = 0; i < max; i++) {
        CBC_QRFinderPattern *center = (CBC_QRFinderPattern*)m_possibleCenters[i];
        if (center->GetCount() >= CENTER_QUORUM) {
            if (firstConfirmedCenter == NULL) {
                firstConfirmedCenter = center;
            } else {
                m_hasSkipped = TRUE;
                return (FX_INT32) ((fabs(firstConfirmedCenter->GetX() - center->GetX()) -
                                    fabs(firstConfirmedCenter->GetY() - center->GetY())) / 2);
            }
        }
    }
    return 0;
}
FX_BOOL CBC_QRFinderPatternFinder::HaveMultiplyConfirmedCenters()
{
    FX_INT32 confirmedCount = 0;
    FX_FLOAT totalModuleSize = 0.0f;
    FX_INT32 max = m_possibleCenters.GetSize();
    FX_INT32 i;
    for (i = 0; i < max; i++) {
        CBC_QRFinderPattern *pattern = (CBC_QRFinderPattern*)m_possibleCenters[i];
        if (pattern->GetCount() >= CENTER_QUORUM) {
            confirmedCount++;
            totalModuleSize += pattern->GetEstimatedModuleSize();
        }
    }
    if (confirmedCount < 3) {
        return FALSE;
    }
    FX_FLOAT average = totalModuleSize / (FX_FLOAT) max;
    FX_FLOAT totalDeviation = 0.0f;
    for (i = 0; i < max; i++) {
        CBC_QRFinderPattern *pattern = (CBC_QRFinderPattern*)m_possibleCenters[i];
        totalDeviation += fabs(pattern->GetEstimatedModuleSize() - average);
    }
    return totalDeviation <= 0.05f * totalModuleSize;
}
inline FX_BOOL centerComparator(FX_LPVOID a, FX_LPVOID b)
{
    return ((CBC_QRFinderPattern*)b)->GetCount() < ((CBC_QRFinderPattern*)a)->GetCount();
}
CFX_PtrArray *CBC_QRFinderPatternFinder::SelectBestpatterns(FX_INT32 &e)
{
    FX_INT32 startSize = m_possibleCenters.GetSize();
    if(m_possibleCenters.GetSize() < 3) {
        e = BCExceptionRead;
        BC_EXCEPTION_CHECK_ReturnValue(e, NULL);
    }
    FX_FLOAT average = 0.0f;
    if(startSize > 3) {
        FX_FLOAT totalModuleSize = 0.0f;
        for(FX_INT32 i = 0; i < startSize; i++) {
            totalModuleSize += ((CBC_QRFinderPattern*)m_possibleCenters[i])->GetEstimatedModuleSize();
        }
        average = totalModuleSize / (FX_FLOAT)startSize;
        for(FX_INT32 j = 0; j < m_possibleCenters.GetSize() && m_possibleCenters.GetSize() > 3; j++) {
            CBC_QRFinderPattern *pattern = (CBC_QRFinderPattern*)m_possibleCenters[j];
            if(fabs(pattern->GetEstimatedModuleSize() - average) > 0.2f * average) {
                delete pattern;
                m_possibleCenters.RemoveAt(j);
                j--;
            }
        }
    }
    if(m_possibleCenters.GetSize() > 3) {
        BC_FX_PtrArray_Sort(m_possibleCenters, centerComparator);
    }
    CFX_PtrArray *vec = FX_NEW CFX_PtrArray();
    vec->SetSize(3);
    (*vec)[0] = ((CBC_QRFinderPattern*)m_possibleCenters[0])->Clone();
    (*vec)[1] = ((CBC_QRFinderPattern*)m_possibleCenters[1])->Clone();
    (*vec)[2] = ((CBC_QRFinderPattern*)m_possibleCenters[2])->Clone();
    return vec;
}