#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <inttypes.h>

const char BASE62[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

char* encode(const uint8_t* input, size_t input_len) {
    if (input_len == 0) {
        return strdup("");
    }

    // Convert input bytes to a big integer
    uint8_t* reversed_input = (uint8_t*)malloc(input_len);
    for (size_t i = 0; i < input_len; i++) {
        reversed_input[i] = input[input_len - i - 1];
    }

    uint64_t value = 0;
    for (size_t i = 0; i < input_len; i++) {
        value = (value << 8) | reversed_input[i];
    }
    free(reversed_input);

    // Encode the big integer to Base62
    char* result = (char*)malloc(input_len * 2 + 1);
    size_t result_len = 0;

    while (value > 0) {
        uint64_t divmod = value % 62;
        result[result_len++] = BASE62[divmod];
        value /= 62;
    }

    // Add leading zeroes
    for (size_t i = 0; i < input_len; i++) {
        if (input[i] == 0) {
            result[result_len++] = BASE62[0];
        } else {
            break;
        }
    }

    result[result_len] = '\0';

    // Reverse the result
    for (size_t i = 0; i < result_len / 2; i++) {
        char temp = result[i];
        result[i] = result[result_len - i - 1];
        result[result_len - i - 1] = temp;
    }

    return result;
}

uint8_t* decode(const char* input, size_t* output_len) {
    if (strlen(input) == 0) {
        *output_len = 0;
        return (uint8_t*)strdup("");
    }

    // Convert Base62 string to a big integer
    uint64_t value = 0;
    size_t input_len = strlen(input);
    for (size_t i = 0; i < input_len; i++) {
        const char* pos = strchr(BASE62, input[i]);
        if (pos) {
            value = value * 62 + (pos - BASE62);
        }
    }

    // Convert big integer to bytes
    size_t bytes_len = (input_len * 6 + 7) / 8;
    uint8_t* bytes = (uint8_t*)malloc(bytes_len);
    for (size_t i = 0; i < bytes_len; i++) {
        bytes[i] = (value >> (8 * (bytes_len - i - 1))) & 0xFF;
    }

    // Add leading zeroes
    size_t leading_zeroes = 0;
    for (size_t i = 0; i < input_len; i++) {
        if (input[i] == BASE62[0]) {
            leading_zeroes++;
        } else {
            break;
        }
    }

    *output_len = leading_zeroes + bytes_len;
    uint8_t* result = (uint8_t*)malloc(*output_len);
    memset(result, 0, leading_zeroes);
    memcpy(result + leading_zeroes, bytes, bytes_len);

    free(bytes);
    return result;
}

int main() {
    const char* input = "回□〓≡╝╚╔╗";
    size_t input_len = strlen(input);
    char* encoded = encode((const uint8_t*)input, input_len);
    printf("Encoded: %s\n", encoded);

    size_t decoded_len;
    uint8_t* decoded = decode(encoded, &decoded_len);
    printf("Decoded: %.*s\n", (int)decoded_len, decoded);

    free(encoded);
    free(decoded);

    return 0;
}