Function LocateErrors

src/bech32.cpp:395–562

Find index of an incorrect character in a Bech32 string. */

/** Find index of an incorrect character in a Bech32 string. */
std::pair<std::string, std::vector<int>> LocateErrors(const std::string& str) {
    std::vector<int> error_locations{};

    if (str.size() > 90) {
        error_locations.resize(str.size() - 90);
        std::iota(error_locations.begin(), error_locations.end(), 90);
        return std::make_pair("Bech32 string too long", std::move(error_locations));
    }

    if (!CheckCharacters(str, error_locations)){
        return std::make_pair("Invalid character or mixed case", std::move(error_locations));
    }

    size_t pos = str.rfind('1');
    if (pos == str.npos) {
        return std::make_pair("Missing separator", std::vector<int>{});
    }
    if (pos == 0 || pos + 7 > str.size()) {
        error_locations.push_back(pos);
        return std::make_pair("Invalid separator position", std::move(error_locations));
    }

    std::string hrp;
    for (size_t i = 0; i < pos; ++i) {
        hrp += LowerCase(str[i]);
    }

    size_t length = str.size() - 1 - pos; // length of data part
    data values(length);
    for (size_t i = pos + 1; i < str.size(); ++i) {
        unsigned char c = str[i];
        int8_t rev = CHARSET_REV[c];
        if (rev == -1) {
            error_locations.push_back(i);
            return std::make_pair("Invalid Base 32 character", std::move(error_locations));
        }
        values[i - pos - 1] = rev;
    }

    // We attempt error detection with both bech32 and bech32m, and choose the one with the fewest errors
    // We can't simply use the segwit version, because that may be one of the errors
    std::optional<Encoding> error_encoding;
    for (Encoding encoding : {Encoding::BECH32, Encoding::BECH32M}) {
        std::vector<int> possible_errors;
        // Recall that (ExpandHRP(hrp) ++ values) is interpreted as a list of coefficients of a polynomial
        // over GF(32). PolyMod computes the "remainder" of this polynomial modulo the generator G(x).
        uint32_t residue = PolyMod(Cat(ExpandHRP(hrp), values)) ^ EncodingConstant(encoding);

        // All valid codewords should be multiples of G(x), so this remainder (after XORing with the encoding
        // constant) should be 0 - hence 0 indicates there are no errors present.
        if (residue != 0) {
            // If errors are present, our polynomial must be of the form C(x) + E(x) where C is the valid
            // codeword (a multiple of G(x)), and E encodes the errors.
            uint32_t syn = Syndrome(residue);

            // Unpack the three 10-bit syndrome values
            int s0 = syn & 0x3FF;
            int s1 = (syn >> 10) & 0x3FF;