#ifndef LFORTRAN_BIGINT_H
#define LFORTRAN_BIGINT_H

#include 

#include 

namespace LCompilers::LPython {

namespace BigInt {

/*
 * Arbitrary size integer implementation.
 *
 * We use tagged signed 64bit integers with no padding bits and using 2's
 * complement for negative values (int64_t) as the underlying data structure.
 * Little-endian is assumed.
 *
 * Bits (from the left):
 * 1 ..... sign: 0 positive, 1 negative
 * 2 ..... tag: bits 1-2 equal to 01: pointer; otherwise integer
 * 3-64 .. if the tag is - integer: rest of the signed integer bits in 2's
 *                                  complement
 *                       - pointer: 64 bit pointer shifted by 2
 *                                  to the right (>> 2)
 *
 * The pointer must be aligned to 4 bytes (bits 63-64 must be 00).
 * Small signed integers are represented directly as integers in int64_t, large
 * integers are allocated on heap and a pointer to it is used as "tag pointer"
 * in int64_t.
 *
 * To check if the integer has a pointer tag, we check that the first two bits
 * (1-2) are equal to 01:
 */

// Returns true if "i" is a pointer and false if "i" is an integer
inline static bool is_int_ptr(int64_t i) {
    return (((uint64_t)i) >> (64 - 2)) == 1;
}

/*
 * A pointer is converted to integer by shifting by 2 to the right and adding
 * 01 to the first two bits to tag it as a pointer:
 */

// Converts a pointer "p" (must be aligned to 4 bytes) to a tagged int64_t
inline static int64_t ptr_to_int(void *p) {
    return (int64_t)( (((uint64_t)p) >> 2) | (1ULL