Advertisement
aaaaaa123456789

JV's programming challenge week 3

Nov 26th, 2012
121
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. typedef struct {
  6.   unsigned char * bytes;
  7.   unsigned length;
  8. } longNumber;
  9.  
  10. void convert(const char *, unsigned char, unsigned char);
  11. void convertBases(const char *, const char *, const char *);
  12.  
  13. char * convertedNumber(const char *, const char *, const char *);
  14. char * baseString(unsigned char);
  15. char * toUppercase(const char *);
  16. unsigned char valueOf(char, const char *);
  17. unsigned char checkBase(const char *);
  18. longNumber convertFrom(const char *, const char *, unsigned char);
  19. char * convertTo(longNumber, const char *, unsigned char);
  20.  
  21. void destroyNumber(longNumber);
  22. longNumber createNumber(unsigned long long);
  23. longNumber copyNumber(longNumber);
  24. unsigned char isZero(longNumber);
  25. longNumber add(longNumber, longNumber);
  26. longNumber addMultiple(longNumber *, unsigned);
  27. longNumber multiplyDigit(longNumber, unsigned char);
  28. longNumber divideDigit(longNumber, unsigned char, unsigned char *);
  29.  
  30. void convert (const char * number, unsigned char baseFrom, unsigned char baseTo) {
  31.   if (!number) return;
  32.   if ((baseFrom < 2) || (baseFrom > 36) || (baseTo < 2) || (baseTo > 36)) return;
  33.   if (baseFrom == baseTo) {
  34.     printf("%s\n", number);
  35.     return;
  36.   }
  37.   unsigned char negative = 0;
  38.   for (; !isalnum(*number); number ++)
  39.     switch (*number) {
  40.       case '-':
  41.         negative = !negative;
  42.         break;
  43.       case '+': case ' ':
  44.         break;
  45.       default:
  46.         return; // error character
  47.     }
  48.   if (!(*number)) return;
  49.   char * from = baseString(baseFrom);
  50.   char * to = baseString(baseTo);
  51.   char * uppercaseNumber = toUppercase(number);
  52.   char * conversionResult = convertedNumber(uppercaseNumber, from, to);
  53.   if (conversionResult) {
  54.     if (negative) putchar('-');
  55.     printf("%s\n", conversionResult);
  56.     free(conversionResult);
  57.   }
  58.   free(uppercaseNumber);
  59.   free(from);
  60.   free(to);
  61. }
  62.  
  63. void convertBases (const char * number, const char * baseFrom, const char * baseTo) {
  64.   if (!number) return;
  65.   char * conversionResult = convertedNumber(number, baseFrom, baseTo);
  66.   if (conversionResult) {
  67.     printf("%s\n", conversionResult);
  68.     free(conversionResult);
  69.   }
  70. }
  71.  
  72.  
  73. char * convertedNumber (const char * number, const char * baseFrom, const char * baseTo) {
  74.   unsigned char from, to;
  75.   from = checkBase(baseFrom);
  76.   if (!from) return NULL;
  77.   to = checkBase(baseTo);
  78.   if (!to) return NULL;
  79.   longNumber converted = convertFrom(number, baseFrom, from);
  80.   if (!converted.length) return NULL;
  81.   char * result = convertTo(converted, baseTo, to);
  82.   destroyNumber(converted);
  83.   return result;
  84. }
  85.  
  86. char * baseString (unsigned char base) {
  87.   if (base < 2) return NULL;
  88.   if (base > 36) return NULL;
  89.   char * result = malloc(base + 1);
  90.   result[base] = 0;
  91.   unsigned char pos;
  92.   for (pos = 0; (pos < base) && (pos < 10); pos ++)
  93.     result[pos] = 48 + pos; // ASCII for the digit
  94.   if (base <= 10) return result;
  95.   for (; pos < base; pos ++)
  96.     result[pos] = 55 + pos; // ASCII for the letter
  97.   return result;
  98. }
  99.  
  100. char * toUppercase (const char * string) {
  101.   // I think there's a strtoupper() somewhere, but that's for pussies
  102.   char * result = malloc(strlen(string) + 1);
  103.   unsigned pos;
  104.   for (pos = 0; string[pos]; pos ++)
  105.     if ((string[pos] >= 97) && (string[pos] <= 122))
  106.       result[pos] = string[pos] - 32;
  107.     else
  108.       result[pos] = string[pos];
  109.   result[pos] = 0;
  110.   return result;
  111. }
  112.  
  113. unsigned char valueOf (char digit, const char * base) {
  114.   unsigned char pos;
  115.   for (pos = 0; base[pos]; pos ++)
  116.     if (digit == base[pos])
  117.       return pos;
  118.   return (unsigned char) -1;
  119. }
  120.  
  121. unsigned char checkBase (const char * base) {
  122.   char checked[256]; // yeah, I'm assuming chars are really 8 bits, kill me
  123.   unsigned pos;
  124.   for (pos = 0; pos < 256; pos ++) checked[pos] = 0;
  125.   for (pos = 0; base[pos]; pos ++)
  126.     if (checked[base[pos]])
  127.       return 0;
  128.     else
  129.       checked[base[pos]] = 1;
  130.   if (pos == 1) return 0; // base 1 is not valid!
  131.   return pos; // return the actual size of the base, because why not
  132. }
  133.  
  134. longNumber convertFrom (const char * number, const char * base, unsigned char baseSize) {
  135.   if (!number) return (longNumber) {NULL, 0};
  136.   if (!(*number)) return (longNumber) {NULL, 0};
  137.   longNumber total = createNumber(0);
  138.   longNumber positionValue = createNumber(1);
  139.   longNumber temp, temp2;
  140.   const char * current = number + (strlen(number) - 1);
  141.   unsigned char digitValue;
  142.   for (; current >= number; current --) {
  143.     digitValue = valueOf(*current, base);
  144.     if (digitValue == (unsigned char) -1) {
  145.       destroyNumber(total);
  146.       destroyNumber(positionValue);
  147.       return (longNumber) {NULL, 0};
  148.     }
  149.     temp = multiplyDigit(positionValue, digitValue);
  150.     temp2 = add(total, temp);
  151.     destroyNumber(total);
  152.     destroyNumber(temp);
  153.     total = temp2;
  154.     temp = multiplyDigit(positionValue, baseSize);
  155.     destroyNumber(positionValue);
  156.     positionValue = temp;
  157.   }
  158.   destroyNumber(positionValue);
  159.   return total;
  160. }
  161.  
  162. char * convertTo (longNumber number, const char * base, unsigned char baseSize) {
  163.   if (isZero(number)) {
  164.     char * result = malloc(2);
  165.     *result = *base;
  166.     result[1] = 0;
  167.     return result;
  168.   }
  169.   unsigned char nextDigit;
  170.   char * result = NULL;
  171.   unsigned resultLength = 0;
  172.   longNumber temp;
  173.   number = copyNumber(number);
  174.   while (!isZero(number)) {
  175.     temp = divideDigit(number, baseSize, &nextDigit);
  176.     destroyNumber(number);
  177.     number = temp;
  178.     result = realloc(result, resultLength + 1);
  179.     result[resultLength ++] = base[nextDigit];
  180.   }
  181.   destroyNumber(number);
  182.   char * reversed = result;
  183.   result = malloc(resultLength + 1);
  184.   unsigned pos;
  185.   for (pos = 0; pos < resultLength; pos ++)
  186.     result[pos] = reversed[resultLength - pos - 1];
  187.   free(reversed);
  188.   result[resultLength] = 0;
  189.   return result;
  190. }
  191.  
  192. // this reminds me of a class definition, but oh well
  193.  
  194. void destroyNumber (longNumber number) {
  195.   if (number.length) free(number.bytes);
  196. }
  197.  
  198. longNumber createNumber (unsigned long long number) {
  199.   if (!number) {
  200.     longNumber result;
  201.     result.length = 1;
  202.     result.bytes = malloc(1);
  203.     *(result.bytes) = 0;
  204.     return result;
  205.   }
  206.   unsigned char * newNumber = malloc(sizeof(unsigned long long));
  207.   unsigned char length;
  208.   for (length = 0; number; length ++, number >>= 8)
  209.     newNumber[length] = number & 255;
  210.   newNumber = realloc(newNumber, length);
  211.   return (longNumber) {newNumber, length};
  212. }
  213.  
  214. longNumber copyNumber (longNumber number) {
  215.   unsigned char * newNumber = malloc(number.length);
  216.   memcpy(newNumber, number.bytes, number.length);
  217.   return (longNumber) {newNumber, number.length};
  218. }
  219.  
  220. unsigned char isZero (longNumber number) {
  221.   unsigned pos;
  222.   for (pos = number.length - 1; pos < number.length; pos --)
  223.     if (number.bytes[pos])
  224.       return 0;
  225.   return 1;
  226. }
  227.  
  228. longNumber add (longNumber number1, longNumber number2) {
  229.   longNumber numbers[2] = {number1, number2};
  230.   return addMultiple(numbers, 2);
  231. }
  232.  
  233. longNumber addMultiple (longNumber * numbers, unsigned amount) {
  234.   unsigned long long total;
  235.   unsigned pos;
  236.   unsigned current;
  237.   unsigned resultLength;
  238.   unsigned char * result;
  239.   if (!amount) return createNumber(0);
  240.   if (amount == 1) return copyNumber(*numbers);
  241.   resultLength = (*numbers).length;
  242.   for (current = 1; current < amount; current ++)
  243.     if ((numbers[current]).length > resultLength)
  244.       resultLength = (numbers[current]).length;
  245.   resultLength += sizeof(unsigned);
  246.   total = 0;
  247.   result = malloc(resultLength);
  248.   for (pos = 0; pos < resultLength; pos ++) {
  249.     for (current = 0; current < amount; current ++)
  250.       total += (pos < (numbers[current]).length) ? ((numbers[current]).bytes[pos]) : 0;
  251.     result[pos] = total & 255;
  252.     total >>= 8; // keeps the carry
  253.   }
  254.   for (; (resultLength > 1) && (!(result[resultLength - 1])); resultLength --);
  255.   result = realloc(result, resultLength);
  256.   return (longNumber) {result, resultLength};
  257. }
  258.  
  259. longNumber multiplyDigit (longNumber number, unsigned char digit) {
  260.   if (!digit) return createNumber(0);
  261.   if (digit == 1) return copyNumber(number);
  262.   unsigned resultLength = number.length + 1;
  263.   unsigned char * result = malloc(resultLength);
  264.   unsigned short total = 0;
  265.   unsigned pos;
  266.   for (pos = 0; pos < number.length; pos ++) {
  267.     total += number.bytes[pos] * digit;
  268.     result[pos] = total & 255;
  269.     total >>= 8;
  270.   }
  271.   result[number.length] = total;
  272.   for (; (resultLength > 1) && (!(result[resultLength - 1])); resultLength --);
  273.   result = realloc(result, resultLength);
  274.   return (longNumber) {result, resultLength};
  275. }
  276.  
  277. longNumber divideDigit (longNumber number, unsigned char divisor, unsigned char * remainder) {
  278.   if (!divisor) return (longNumber) {NULL, 0}; // BLACKHOLE!!!
  279.   if (divisor == 1) {
  280.     if (remainder) *remainder = 0;
  281.     return copyNumber(number);
  282.   }
  283.   unsigned resultLength = number.length;
  284.   unsigned char * result = malloc(resultLength);
  285.   unsigned pos;
  286.   unsigned short total = 0;
  287.   for (pos = resultLength - 1; pos < resultLength /* -1 = 4294967295 or so */; pos --) {
  288.     total <<= 8;
  289.     total += number.bytes[pos];
  290.     result[pos] = total / divisor;
  291.     total %= divisor;
  292.   }
  293.   if (remainder) *remainder = total;
  294.   for (; (resultLength > 1) && (!(result[resultLength - 1])); resultLength --);
  295.   result = realloc(result, resultLength);
  296.   return (longNumber) {result, resultLength};
  297. }
Advertisement
RAW Paste Data Copied
Advertisement