text: #include "conversion.h"
  #include <stdint.h>
  #include "common.h"
  
  // #define USE_UNSAFE_INCREMENT_TAG
  
  #define INT_LENGTH 12
  // base of the ternary system
  #define BASE 3
  
  // the middle of the domain described by 242 trits, i.e. \sum_{k=0}^{241} 3^k
  static const uint32_t HALF_3[12] = {
      0xa5ce8964, 0x9f007669, 0x1484504f, 0x3ade00d9, 0x0c24486e, 0x50979d57,
      0x79a4c702, 0x48bbae36, 0xa9f6808b, 0xaa06a805, 0xa87fabdf, 0x5e69ebef};
  
  // the two's complement of HALF_3_u, i.e. ~HALF_3_u + 1
  static const uint32_t NEG_HALF_3[12] = {
      0x5a31769c, 0x60ff8996, 0xeb7bafb0, 0xc521ff26, 0xf3dbb791, 0xaf6862a8,
      0x865b38fd, 0xb74451c9, 0x56097f74, 0x55f957fa, 0x57805420, 0xa1961410};
  
  // representing the value of the highes trit in the feasible domain, i.e 3^242
  static const uint32_t TRIT_243[12] = {
      0x4b9d12c9, 0x3e00ecd3, 0x2908a09f, 0x75bc01b2, 0x184890dc, 0xa12f3aae,
      0xf3498e04, 0x91775c6c, 0x53ed0116, 0x540d500b, 0x50ff57bf, 0xbcd3d7df};
  
  #ifdef USE_UNSAFE_INCREMENT_TAG
  // representing the value of the 82nd trit, i.e. 3^81
  static const uint32_t TRIT_82[12] = {0xd56d7cc3, 0xb6bf0c69, 0xa149e834,
                                       0x4d98d5ce, 0x1};
  #endif // USE_UNSAFE_INCREMENT_TAG
  
  mutex_t iota_wallet_trits_mutex;
  
  void conversion_mutex_init(void){
      mutex_init(&iota_wallet_trits_mutex, NULL);
  }
  
  trit_t trits_buffer[243];
  void clear_trits_buffer(void){
      memset(trits_buffer, -1, 243);
  }
  
  static const trit_t trits_mapping[27][3] = {
      {-1, -1, -1}, {0, -1, -1}, {1, -1, -1}, {-1, 0, -1}, {0, 0, -1}, {1, 0, -1},
      {-1, 1, -1},  {0, 1, -1},  {1, 1, -1},  {-1, -1, 0}, {0, -1, 0}, {1, -1, 0},
      {-1, 0, 0},   {0, 0, 0},   {1, 0, 0},   {-1, 1, 0},  {0, 1, 0},  {1, 1, 0},
      {-1, -1, 1},  {0, -1, 1},  {1, -1, 1},  {-1, 0, 1},  {0, 0, 1},  {1, 0, 1},
      {-1, 1, 1},   {0, 1, 1},   {1, 1, 1}};
  
  // available tryte chars in the correct order
  static const char tryte_to_char_mapping[] = "NOPQRSTUVWXYZ9ABCDEFGHIJKLM";
  
  /* --------------------- trits > trytes and back */
  // used for bytes to chars and back
  int trytes_to_trits(const tryte_t trytes_in[], trit_t trits_out[],
                      unsigned int tryte_len)
  {
      unsigned int i;
  
      for (i = 0; i < tryte_len; i++) {
          int8_t idx = (int8_t)trytes_in[i] + 13;
          trits_out[i * 3 + 0] = trits_mapping[idx][0];
          trits_out[i * 3 + 1] = trits_mapping[idx][1];
          trits_out[i * 3 + 2] = trits_mapping[idx][2];
      }
      return 0;
  }
  
  int trits_to_trytes(const trit_t trits_in[], tryte_t trytes_out[],
                      unsigned int trit_len)
  {
      if (trit_len % 3 != 0) {
          return -1;
      }
      unsigned int tryte_len = trit_len / 3;
      unsigned int i;
  
      for (i = 0; i < tryte_len; i++) {
          trytes_out[i] = trits_in[i * 3 + 0] + trits_in[i * 3 + 1] * 3 +
                          trits_in[i * 3 + 2] * 9;
      }
      return 0;
  }
  /* --------------------- END trits > trytes */
  
  /* --------------------- trytes > chars and back */
  // used for bytes to chars and back
  int chars_to_trytes(const char chars_in[], tryte_t trytes_out[],
                      unsigned int len)
  {
      unsigned int i;
  
      for (i = 0; i < len; i++) {
          if (chars_in[i] == '9') {
              trytes_out[i] = 0;
          }
          else if ((int8_t)chars_in[i] >= 'N') {
              trytes_out[i] = (int8_t)(chars_in[i]) - 64 - 27;
          }
          else {
              trytes_out[i] = (int8_t)(chars_in[i]) - 64;
          }
      }
      return 0;
  }
  
  int trytes_to_chars(const tryte_t trytes_in[], char chars_out[],
                      unsigned int len)
  {
      unsigned int i;
  
      for (i = 0; i < len; i++) {
          chars_out[i] = tryte_to_char_mapping[trytes_in[i] + 13];
      }
  
      return 0;
  }
  /* --------------------- END trytes > chars */
  
  void chars_to_trits(const char *chars, trit_t *trits, unsigned int chars_len)
  {
      tryte_t trytes[chars_len];
      chars_to_trytes(chars, trytes, chars_len);
      trytes_to_trits(trytes, trits, chars_len);
  }
  
  void trits_to_chars(const trit_t *trits, char *chars, unsigned int trit_len)
  {
      tryte_t trytes[trit_len / 3];
      trits_to_trytes(trits, trytes, trit_len);
      trytes_to_chars(trytes, chars, trit_len / 3);
  }
  
  char *int64_to_chars(int64_t value, char *chars, unsigned int num_trytes) {
      trit_t trits[num_trytes * 3];
      int64_to_trits(value, trits, num_trytes * 3);
      trits_to_chars(trits, chars, num_trytes * 3);
  
      return chars + num_trytes;
  }
  
  void chars_to_int64(const char chars_in[], int64_t *value, unsigned int len)
  {
      trit_t trits[len * 3];
  
      chars_to_trits(chars_in, trits, len);
      trits_to_int64(trits, sizeof(trits), value);
  }
  
  /** @brief Returns true, if the long little-endian integer represents a negative
   *         number in two's complement.
   */
  static inline bool bigint_is_negative(const uint32_t *bigint)
  {
      // whether the most significant bit of the most significant byte is set
      return (bigint[12 - 1] >> (sizeof(bigint[0]) * 8 - 1) != 0);
  }
  
  static int bigint_cmp(const uint32_t *a, const uint32_t *b)
  {
      unsigned int i;
  
      for (i = 12; i-- > 0;) {
          if (a[i] < b[i]) {
              return -1;
          }
          if (a[i] > b[i]) {
              return 1;
          }
      }
      return 0;
  }
  
  static inline bool addcarry_u32(uint32_t *r, uint32_t a, uint32_t b, bool c_in)
  {
      const uint32_t sum = a + b + (c_in ? 1 : 0);
      const bool carry = (sum < a) || (c_in && (sum <= a));
  
      *r = sum;
      return carry;
  }
  
  static bool bigint_add(uint32_t *r, const uint32_t *a, const uint32_t *b)
  {
      bool carry = false;
      unsigned int i;
      for (i = 0; i < 12; i++) {
          carry = addcarry_u32(&r[i], a[i], b[i], carry);
      }
  
      return carry;
  }
  
  static bool bigint_sub(uint32_t *r, const uint32_t *a, const uint32_t *b)
  {
      bool carry = true;
      unsigned int i;
      for (i = 0; i < 12; i++) {
          carry = addcarry_u32(&r[i], a[i], ~b[i], carry);
      }
  
      return carry;
  }
  
  /** @brief adds a single 32-bit integer to a long little-endian integer.
   *  @return index of the most significant word which changed during the addition
   */
  unsigned int bigint_add_u32_mem(uint32_t *a, uint32_t summand)
  {
      bool carry = addcarry_u32(&a[0], a[0], summand, false);
      unsigned int i;
      if (carry == false) {
          return 0;
      }
  
      for (i = 1; i < 12; i++) {
          carry = addcarry_u32(&a[i], a[i], 0, true);
          if (carry == false) {
              return i;
          }
      }
  
      // overflow
      return 12;
  }
  
  /** @brief multiplies a single 8-bit integer with a long little-endian integer.
   *  @param ms_index the index of the most significant non-zero word of the
   *                  input integer. Words after this are not considered.
   *  @return the carry (one word) of the multiplication up to the byte which has
              the index specified in msb_index.
   */
  static uint32_t bigint_mult_byte_mem(uint32_t *a, uint8_t factor,
                                       unsigned int ms_index)
  {
      uint32_t carry = 0;
      unsigned int i;
  
      for (i = 0; i <= ms_index; i++) {
          const uint64_t v = (uint64_t)factor * a[i] + carry;
  
          carry = v >> 32;
          a[i] = v & 0xFFFFFFFF;
      }
  
      return carry;
  }
  
  /** @brief devides a long big-endian integer by a single 8-bit integer.
   *  @return remainder of the integer division.
   */
  static uint32_t bigint_div_byte_mem(uint32_t *a, uint8_t divisor)
  {
      uint32_t remainder = 0;
      unsigned int i;
  
      for (i = 12; i-- > 0;) {
          const uint64_t v = UINT64_C(0x100000000) * remainder + a[i];
  
          remainder = v % divisor;
          a[i] = (v / divisor) & 0xFFFFFFFF;
      }
  
      return remainder;
  }
  
  /** @brief Changes number to the corresponding representation of the number
   *         with the 242th trit set to 0.
   * @return true, if the number was changed, false otherwise.
   */
  static bool bigint_set_last_trit_zero(uint32_t *bigint)
  {
      if (bigint_is_negative(bigint)) {
          if (bigint_cmp(bigint, NEG_HALF_3) < 0) {
              bigint_add(bigint, bigint, TRIT_243);
              return true;
          }
      }
      else {
          if (bigint_cmp(bigint, HALF_3) > 0) {
              bigint_sub(bigint, bigint, TRIT_243);
              return true;
          }
      }
      return false;
  }
  
  /* --------------------- trits > bigint and back */
  static void trits_to_bigint(const trit_t *trits, uint32_t *bigint)
  {
      unsigned int ms_index = 0; // initialy there is no most significant word >0
      unsigned int i;
      memset(bigint, 0, 12 * sizeof(bigint[0]));
  
      // ignore the 243th trit, as it cannot be fully represented in 48 bytes
      for (i = 242; i-- > 0;) {
          // convert to non-balanced ternary
          const uint8_t trit = trits[i] + 1;
  
          const uint32_t carry = bigint_mult_byte_mem(bigint, BASE, ms_index);
          if (carry > 0) {
              // if there is carry we need to use the next higher byte
              bigint[++ms_index] = carry;
          }
  
          if (trit == 0) {
              // nothing to add
              continue;
          }
  
          const unsigned int last_changed_index =
              bigint_add_u32_mem(bigint, trit);
          if (last_changed_index > ms_index) {
              ms_index = last_changed_index;
          }
      }
  
      // convert to balanced ternary using two's complement
      if (bigint_cmp(bigint, HALF_3) >= 0) {
          bigint_sub(bigint, bigint, HALF_3);
      }
      else {
          // equivalent to bytes := ~(HALF_3 - bytes) + 1
          bigint_add(bigint, NEG_HALF_3, bigint);
      }
  }
  
  static void bigint_to_trits_mem(uint32_t *bigint, trit_t *trits)
  {
      unsigned int i;
  
      // the two's complement represention is only correct, if the number fits
      // into 48 bytes, i.e. has the 243th trit set to 0
      bigint_set_last_trit_zero(bigint);
  
      // convert to the (positive) number representing non-balanced ternary
      if (bigint_is_negative(bigint)) {
          bigint_sub(bigint, bigint, NEG_HALF_3);
      }
      else {
          bigint_add(bigint, bigint, HALF_3);
      }
  
      // ignore the 243th trit, as it cannot be fully represented in 48 bytes
      for (i = 0; i < 242; i++) {
          const uint32_t rem = bigint_div_byte_mem(bigint, BASE);
          trits[i] = rem - 1; // convert back to balanced
      }
      // set the last trit to zero for consistency
      trits[242] = 0;
  }
  
  bool int64_to_trits(int64_t value, trit_t *trits, unsigned int num_trits)
  {
      const bool is_negative = value < 0;
      unsigned int i;
      if (is_negative) {
          value = -value;
      }
  
      memset(trits, 0, num_trits);
  
      for (i = 0; i < num_trits; i++) {
          if (value == 0) {
              return false;
          }
  
          int rem = value % BASE;
          value = value / BASE;
          if (rem > 1) {
              rem = -1;
              value += 1;
          }
  
          trits[i] = is_negative ? -rem : rem;
      }
  
      return value != 0;
  }
  
  void trits_to_int64(trit_t *trits, unsigned int num_trits, int64_t *value)
  {
      *value = 0;
      while (num_trits-- > 0) {
          *value = *value * BASE + trits[num_trits];
      }
  }
  /* --------------------- END trits > bigint */
  
  /** @brief Converts bigint consisting of 12 words into an array of bytes.
   *  It is represented using 48bytes in big-endiean, by reversing the order of
   *  the words. The endianness of the host machine is taken into account.
   */
  static void bigint_to_bytes(const uint32_t *bigint, unsigned char *bytes)
  {
      unsigned int i;
  
      // reverse word order
      for (i = 12; i-- > 0; bytes += 4) {
          const uint32_t num = bigint[i];
  
          bytes[0] = (num >> 24) & 0xFF;
          bytes[1] = (num >> 16) & 0xFF;
          bytes[2] = (num >> 8) & 0xFF;
          bytes[3] = (num >> 0) & 0xFF;
      }
  }
  
  /** @brief Converts an array of 48 bytes into a bigint consisting of 12 words.
   *  The bigint is represented using 48bytes in big-endiean. The endianness of
   * the host machine is taken into account.
   */
  static void bytes_to_bigint(const unsigned char *bytes, uint32_t *bigint)
  {
      unsigned int i;
  
      // reverse word order
      for (i = 12; i-- > 0; bytes += 4) {
          bigint[i] = (uint32_t)bytes[0] << 24 | (uint32_t)bytes[1] << 16 |
                      (uint32_t)bytes[2] << 8 | (uint32_t)bytes[3] << 0;
      }
  }
  
  void trits_to_bytes(const trit_t *trits, unsigned char *bytes)
  {
      uint32_t bigint[12];
      trits_to_bigint(trits, bigint);
      bigint_to_bytes(bigint, bytes);
  }
  
  void trytes_to_bytes(const tryte_t *trytes, unsigned char *bytes)
  {
      //trit_t trits_buffer[243];
      mutex_lock(&iota_wallet_trits_mutex);
      clear_trits_buffer();
      trytes_to_trits(trytes, trits_buffer, 81);
      trits_to_bytes(trits_buffer, bytes);
      mutex_unlock(&iota_wallet_trits_mutex);
  }
  
  
  void chars_to_bytes(const char *chars, unsigned char *bytes,
                      unsigned int chars_len)
  {
      unsigned int i;
  
      mutex_lock(&iota_wallet_trits_mutex);
      clear_trits_buffer();
      for (i = 0; i < chars_len / 81; i++) {
  
          chars_to_trits(chars + i * 81, trits_buffer, 81);
          // bigint can only handle 242 trits
          trits_buffer[242] = 0;
  
          trits_to_bytes(trits_buffer, bytes + i * 48);
      }
      mutex_unlock(&iota_wallet_trits_mutex);
  }
  
  static inline void bytes_to_trits(const unsigned char *bytes, trit_t *trits)
  {
      uint32_t bigint[12];
      bytes_to_bigint(bytes, bigint);
      bigint_to_trits_mem(bigint, trits);
  }
  
  void bytes_to_trytes(const unsigned char *bytes, tryte_t *trytes)
  {
      mutex_lock(&iota_wallet_trits_mutex);
      clear_trits_buffer();
      bytes_to_trits(bytes, trits_buffer);
      trits_to_trytes(trits_buffer, trytes, 243);
      mutex_unlock(&iota_wallet_trits_mutex);
  }
  
  void bytes_to_chars(const unsigned char *bytes, char *chars,
                      unsigned int bytes_len)
  {
      unsigned int i;
  
      for (i = 0; i < bytes_len / 48; i++) {
          tryte_t trytes[81];
          bytes_to_trytes(bytes + i * 48, trytes);
          trytes_to_chars(trytes, chars + i * 81, 81);
      }
  }
  
  void bytes_set_last_trit_zero(unsigned char *bytes)
  {
      uint32_t bigint[12];
      bytes_to_bigint(bytes, bigint);
      if (bigint_set_last_trit_zero(bigint)) {
          bigint_to_bytes(bigint, bytes);
      }
  }
  
  static void increment_trit_aera(trit_t *trits, unsigned int start_trit,
                                  unsigned int num_trits)
  {
      trit_t *trit = trits + start_trit;
      unsigned int i;
  
      for (i = 0; i < num_trits; i++, trit++) {
          if (*trit < MAX_TRIT_VALUE) {
              *trit += 1;
              break;
          }
          *trit = MIN_TRIT_VALUE;
      }
  }
  
  // TODO: there are faster and more efficient algos for this, but is it worth it?
  void bytes_increment_trit_area_81(unsigned char *bytes)
  {
  #ifdef USE_UNSAFE_INCREMENT_TAG
      uint32_t bigint[12];
      bytes_to_bigint(bytes, bigint);
      bigint_add(bigint, bigint, TRIT_82);
      bigint_to_bytes(bigint, bytes);
  #else
      trit_t trits[243];
      bytes_to_trits(bytes, trits);
      increment_trit_aera(trits, 81, 81);
      trits_to_bytes(trits, bytes);
  #endif // USE_UNSAFE_INCREMENT_TAG
  }
  
  void bytes_add_u32_mem(unsigned char *bytes, uint32_t summand)
  {
      if (summand > 0) {
          uint32_t bigint[12];
  
          bytes_to_bigint(bytes, bigint);
          bigint_add_u32_mem(bigint, summand);
          bigint_set_last_trit_zero(bigint);
          bigint_to_bytes(bigint, bytes);
      }
  }
  
  int tryte_chars_validate(const char chars_in[], unsigned int len)
  {
      unsigned int i;
  
      for (i = 0; i < len; i++) {
          if ((chars_in[i] != '9') &&
                  ((chars_in[i] < 'A') || (chars_in[i] > 'Z'))) {
              return -1;
          }
      }
      return 0;
  }
  
  void chars_increment(char chars_in[], unsigned int len)
  {
      unsigned int i;
  
      for (i = 0; i < len; i++) {
          if (chars_in[i] == '9') {
              chars_in[i] = 'A';
              break;
          }
          else if (chars_in[i] == 'Z') {
              chars_in[i] = '9';
              break;
          }
          else if (chars_in[i] == 'M') {
              chars_in[i] = 'N';
          }
          else {
              chars_in[i]++;
              break;
          }
      }
  }
  