251    }
252    return SYNDROME_CONSTS;
253}
254constexpr std::array<uint32_t, 25> SYNDROME_CONSTS = GenerateSyndromeConstants();
255
256/**
257 * Syndrome returns the three values s_997, s_998, and s_999 described above,
258 * packed into a 30-bit integer, where each group of 10 bits encodes one value.
259 */
260uint32_t Syndrome(const uint32_t residue) {
261    // low is the first 5 bits, corresponding to the r6 in the residue
262    // (the constant term of the polynomial).
263    uint32_t low = residue & 0x1f;
264
265    // We begin by setting s_j = low = r6 for all three values of j, because these are unconditional.
266    uint32_t result = low ^ (low << 10) ^ (low << 20);
267
268    // Then for each following bit, we add the corresponding precomputed constant if the bit is 1.
269    // For example, 0x31edd3c4 is 1100011110 1101110100 1111000100 when unpacked in groups of 10
270    // bits, corresponding exactly to a^999 || a^998 || a^997 (matching the corresponding values in
271    // GF1024_EXP above). In this way, we compute all three values of s_j for j in (997, 998, 999)
272    // simultaneously. Recall that XOR corresponds to addition in a characteristic 2 field.
273    for (int i = 0; i < 25; ++i) {
274        result ^= ((residue >> (5+i)) & 1 ? SYNDROME_CONSTS.at(i) : 0);
275    }
276    return result;
277}
278
279/** Convert to lower case. */
280inline unsigned char LowerCase(unsigned char c)
281{
282    return (c >= 'A' && c <= 'Z') ? (c - 'A') + 'a' : c;
283}
284
285/** Return indices of invalid characters in a Bech32 string. */
286bool CheckCharacters(const std::string& str, std::vector<int>& errors)
287{
288    bool lower = false, upper = false;
289    for (size_t i = 0; i < str.size(); ++i) {
290        unsigned char c{(unsigned char)(str[i])};
291        if (c >= 'a' && c <= 'z') {
292            if (upper) {
293                errors.push_back(i);
294            } else {
295                lower = true;
296            }
297        } else if (c >= 'A' && c <= 'Z') {
298            if (lower) {
299                errors.push_back(i);
300            } else {
301                upper = true;
302            }
303        } else if (c < 33 || c > 126) {
304            errors.push_back(i);
305        }
306    }
307    return errors.empty();
308}
309
310std::vector<unsigned char> PreparePolynomialCoefficients(const std::string& hrp, const data& values)
311{
312    data ret;
313    ret.reserve(hrp.size() + 1 + hrp.size() + values.size() + CHECKSUM_SIZE);
314
315    /** Expand a HRP for use in checksum computation. */
316    for (size_t i = 0; i < hrp.size(); ++i) ret.push_back(hrp[i] >> 5);
317    ret.push_back(0);
318    for (size_t i = 0; i < hrp.size(); ++i) ret.push_back(hrp[i] & 0x1f);
319
320    ret.insert(ret.end(), values.begin(), values.end());
321
322    return ret;
323}
324
325/** Verify a checksum. */
326Encoding VerifyChecksum(const std::string& hrp, const data& values)
327{
328    // PolyMod computes what value to xor into the final values to make the checksum 0. However,
329    // if we required that the checksum was 0, it would be the case that appending a 0 to a valid
330    // list of values would result in a new valid list. For that reason, Bech32 requires the
331    // resulting checksum to be 1 instead. In Bech32m, this constant was amended. See
332    // https://gist.github.com/sipa/14c248c288c3880a3b191f978a34508e for details.
333    auto enc = PreparePolynomialCoefficients(hrp, values);
334    const uint32_t check = PolyMod(enc);
335    if (check == EncodingConstant(Encoding::BECH32)) return Encoding::BECH32;
336    if (check == EncodingConstant(Encoding::BECH32M)) return Encoding::BECH32M;
337    return Encoding::INVALID;
338}
339
340/** Create a checksum. */
341data CreateChecksum(Encoding encoding, const std::string& hrp, const data& values)
342{
343    auto enc = PreparePolynomialCoefficients(hrp, values);
344    enc.insert(enc.end(), CHECKSUM_SIZE, 0x00);
345    uint32_t mod = PolyMod(enc) ^ EncodingConstant(encoding); // Determine what to XOR into those 6 zeroes.
346    data ret(CHECKSUM_SIZE);
347    for (size_t i = 0; i < CHECKSUM_SIZE; ++i) {
348        // Convert the 5-bit groups in mod to checksum values.
349        ret[i] = (mod >> (5 * (5 - i))) & 31;
350    }
351    return ret;
352}
353
354} // namespace
355
356/** Encode a Bech32 or Bech32m string. */
357std::string Encode(Encoding encoding, const std::string& hrp, const data& values) {
358    // First ensure that the HRP is all lowercase. BIP-173 and BIP350 require an encoder
359    // to return a lowercase Bech32/Bech32m string, but if given an uppercase HRP, the
360    // result will always be invalid.
361    for (const char& c : hrp) assert(c < 'A' || c > 'Z');
362
363    std::string ret;
364    ret.reserve(hrp.size() + 1 + values.size() + CHECKSUM_SIZE);
365    ret += hrp;
366    ret += SEPARATOR;
367    for (const uint8_t& i : values) ret += CHARSET[i];
368    for (const uint8_t& i : CreateChecksum(encoding, hrp, values)) ret += CHARSET[i];
369    return ret;
370}
371
372/** Decode a Bech32 or Bech32m string. */
373DecodeResult Decode(const std::string& str, CharLimit limit) {
374    std::vector<int> errors;
375    if (!CheckCharacters(str, errors)) return {};
376    size_t pos = str.rfind(SEPARATOR);
377    if (str.size() > limit) return {};
378    if (pos == str.npos || pos == 0 || pos + CHECKSUM_SIZE >= str.size()) {
379        return {};
380    }
381    data values(str.size() - 1 - pos);
382    for (size_t i = 0; i < str.size() - 1 - pos; ++i) {
383        unsigned char c = str[i + pos + 1];
384        int8_t rev = CHARSET_REV[c];
385
386        if (rev == -1) {
387            return {};
388        }
389        values[i] = rev;
390    }
391    std::string hrp;
392    hrp.reserve(pos);
393    for (size_t i = 0; i < pos; ++i) {
394        hrp += LowerCase(str[i]);
395    }
396    Encoding result = VerifyChecksum(hrp, values);
397    if (result == Encoding::INVALID) return {};
398    return {result, std::move(hrp), data(values.begin(), values.end() - CHECKSUM_SIZE)};
399}
400
401/** Find index of an incorrect character in a Bech32 string. */
402std::pair<std::string, std::vector<int>> LocateErrors(const std::string& str, CharLimit limit) {
403    std::vector<int> error_locations{};
404
405    if (str.size() > limit) {
406        error_locations.push_back(static_cast<int>(limit));
407        return std::make_pair("Bech32 string too long", std::move(error_locations));
408    }
409
410    if (!CheckCharacters(str, error_locations)){
411        return std::make_pair("Invalid character or mixed case", std::move(error_locations));
412    }
413
414    size_t pos = str.rfind(SEPARATOR);
415    if (pos == str.npos) {
416        return std::make_pair("Missing separator", std::vector<int>{});
417    }
418    if (pos == 0 || pos + CHECKSUM_SIZE >= str.size()) {
419        error_locations.push_back(pos);
420        return std::make_pair("Invalid separator position", std::move(error_locations));
421    }
422
423    std::string hrp;
424    hrp.reserve(pos);
425    for (size_t i = 0; i < pos; ++i) {
426        hrp += LowerCase(str[i]);
427    }
428
429    size_t length = str.size() - 1 - pos; // length of data part
430    data values(length);
431    for (size_t i = pos + 1; i < str.size(); ++i) {
432        unsigned char c = str[i];
433        int8_t rev = CHARSET_REV[c];
434        if (rev == -1) {
435            error_locations.push_back(i);
436            return std::make_pair("Invalid Base 32 character", std::move(error_locations));
437        }
438        values[i - pos - 1] = rev;
439    }
440
441    // We attempt error detection with both bech32 and bech32m, and choose the one with the fewest errors
442    // We can't simply use the segwit version, because that may be one of the errors
443    std::optional<Encoding> error_encoding;
444    for (Encoding encoding : {Encoding::BECH32, Encoding::BECH32M}) {
445        std::vector<int> possible_errors;
446        // Recall that (expanded hrp + values) is interpreted as a list of coefficients of a polynomial
447        // over GF(32). PolyMod computes the "remainder" of this polynomial modulo the generator G(x).
448        auto enc = PreparePolynomialCoefficients(hrp, values);
449        uint32_t residue = PolyMod(enc) ^ EncodingConstant(encoding);
450
451        // All valid codewords should be multiples of G(x), so this remainder (after XORing with the encoding
452        // constant) should be 0 - hence 0 indicates there are no errors present.
453        if (residue != 0) {
454            // If errors are present, our polynomial must be of the form C(x) + E(x) where C is the valid
455            // codeword (a multiple of G(x)), and E encodes the errors.
456            uint32_t syn = Syndrome(residue);
457
458            // Unpack the three 10-bit syndrome values
459            int s0 = syn & 0x3FF;
460            int s1 = (syn >> 10) & 0x3FF;
461            int s2 = syn >> 20;
462
463            // Get the discrete logs of these values in GF1024 for more efficient computation
464            int l_s0 = GF1024_LOG.at(s0);
465            int l_s1 = GF1024_LOG.at(s1);
466            int l_s2 = GF1024_LOG.at(s2);
467
468            // First, suppose there is only a single error. Then E(x) = e1*x^p1 for some position p1
469            // Then s0 = E((e)^997) = e1*(e)^(997*p1) and s1 = E((e)^998) = e1*(e)^(998*p1)
470            // Therefore s1/s0 = (e)^p1, and by the same logic, s2/s1 = (e)^p1 too.
471            // Hence, s1^2 == s0*s2, which is exactly the condition we check first:
472            if (l_s0 != -1 && l_s1 != -1 && l_s2 != -1 && (2 * l_s1 - l_s2 - l_s0 + 2046) % 1023 == 0) {
473                // Compute the error position p1 as l_s1 - l_s0 = p1 (mod 1023)
474                size_t p1 = (l_s1 - l_s0 + 1023) % 1023; // the +1023 ensures it is positive
475                // Now because s0 = e1*(e)^(997*p1), we get e1 = s0/((e)^(997*p1)). Remember that (e)^1023 = 1,
476                // so 1/((e)^997) = (e)^(1023-997).
477                int l_e1 = l_s0 + (1023 - 997) * p1;
478                // Finally, some sanity checks on the result:
479                // - The error position should be within the length of the data
480                // - e1 should be in GF(32), which implies that e1 = (e)^(33k) for some k (the 31 non-zero elements
481                // of GF(32) form an index 33 subgroup of the 1023 non-zero elements of GF(1024)).
482                if (p1 < length && !(l_e1 % 33)) {
483                    // Polynomials run from highest power to lowest, so the index p1 is from the right.
484                    // We don't return e1 because it is dangerous to suggest corrections to the user,
485                    // the user should check the address themselves.
486                    possible_errors.push_back(str.size() - p1 - 1);
487                }
488            // Otherwise, suppose there are two errors. Then E(x) = e1*x^p1 + e2*x^p2.
489            } else {
490                // For all possible first error positions p1
491                for (size_t p1 = 0; p1 < length; ++p1) {
492                    // We have guessed p1, and want to solve for p2. Recall that E(x) = e1*x^p1 + e2*x^p2, so
493                    // s0 = E((e)^997) = e1*(e)^(997^p1) + e2*(e)^(997*p2), and similar for s1 and s2.
494                    //
495                    // Consider s2 + s1*(e)^p1
496                    //          = 2e1*(e)^(999^p1) + e2*(e)^(999*p2) + e2*(e)^(998*p2)*(e)^p1
497                    //          = e2*(e)^(999*p2) + e2*(e)^(998*p2)*(e)^p1
498                    //    (Because we are working in characteristic 2.)
499                    //          = e2*(e)^(998*p2) ((e)^p2 + (e)^p1)
500                    //