util.c

   1 /*
   2    Cantaveria - action adventure platform game
   3    Copyright (C) 2009 2010 Evan Rinehart
   4
   5    This program is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU General Public License
   7    as published by the Free Software Foundation; either version 2
   8    of the License, or (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program; if not, write to
  17
  18    The Free Software Foundation, Inc.
  19    51 Franklin Street, Fifth Floor
  20    Boston, MA  02110-1301, USA
  21 */
  22
  23
  24 #include <stdio.h>
  25 #include <stdarg.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28 #include <limits.h>
  29
  30 #include <rng.h>
  31 #include <util.h>
  32
  33 /* error reporting */
  34 void report_verror(const char* format, va_list ap){
  35         vprintf(format, ap);
  36 }
  37
  38 void report_error(const char* format, ...){
  39         va_list ap;
  40         va_start(ap, format);
  41         report_verror(format, ap);
  42         va_end(ap);
  43 }
  44
  45 void fatal_error(const char* format, ...){
  46         va_list ap;
  47         va_start(ap, format);
  48         report_verror(format, ap);
  49         va_end(ap);
  50         exit(-1);
  51 }
  52
  53 void out_of_memory(const char* prefix){
  54         report_error("%s: *out of memory*\n", prefix);
  55         exit(-2);
  56 }
  57
  58 /* 'safe' functions */
  59 void* xmalloc(size_t size){
  60         void* v = malloc(size);
  61         if(!v){
  62                 /* On Linux malloc by default does not return NULL
  63                 even if there is no more memory. So this function
  64                 isn't really 'safe' on that system. */
  65                 out_of_memory("xmalloc");
  66         }
  67         return v;
  68 }
  69
  70 char* strxcpy(const char* str){
  71         char* cpy = xmalloc(strlen(str)+1);
  72         strcpy(cpy, str);
  73         return cpy;
  74 }
  75
  76 void strmcat(char* dst, const char* src, size_t n){
  77         strncat(dst, src, n - strlen(src) - 1);
  78 }
  79
  80
  81
  82
  83 /*
  84    decodes utf8 encoded string str and places the
  85    next character in u.
  86    returns the number of bytes of str consumed.
  87 */
  88 int unicode_getc(char* str, utf32* u){
  89         /*unsigned char b[4] = {str[0], str[1], str[2], str[3]};*/
  90         unsigned char b[4];
  91         unsigned char a[4] = {0,0,0,0};
  92         int N;
  93
  94         memcpy(b, str, 4);
  95
  96         /* 1111 0xf
  97            1110 0xe
  98            1100 0xc
  99            1000 0x8 */
 100
 101         if((b[0] & 0x80) == 0){ /*one byte sequence*/
 102                 a[3] = b[0];
 103                 N = 1;
 104         }
 105
 106         else if(
 107                 ((b[0]&0xe0)==0xc0) &&
 108                 ((b[1]&0xc0)==0x80)
 109         ){
 110                 /*two byte sequence*/
 111                 a[3] = ((b[0]&0x03)<<6)|(b[1]&0x3f);
 112                 a[2] = (b[0]&0x1c)>>2;
 113                 N = 2;
 114         }
 115
 116         else if(
 117                 ((b[0]&0xf0)==0xe0) &&
 118                 ((b[1]&0xc0)==0x80) &&
 119                 ((b[2]&0xc0)==0x80)
 120         ){
 121                 /*three byte sequence*/
 122                 a[3] = ((b[1]&0x03)<<6)|(b[2]&0x3f);
 123                 a[2] = ((b[0]&0x0f)<<4)|((b[1]&0x3c)>>2);
 124                 N = 3;
 125         }
 126
 127         else if(
 128                 ((b[0]&0xf8)==0xf0) &&
 129                 ((b[1]&0xc0)==0x80) &&
 130                 ((b[2]&0xc0)==0x80) &&
 131                 ((b[3]&0xc0)==0x80)
 132         ){
 133                 /*four byte sequence*/
 134                 a[3] = ((b[2]&0x03)<<6)|(b[3]&0x3f);
 135                 a[2] = ((b[1]&0x0f)<<4)|((b[2]&0x3c)>>2);
 136                 a[1] = ((b[0]&0x03)<<2)|((b[1]&0x30)>>4);
 137                 N = 4;
 138         }
 139
 140         else {
 141                 a[3] = '?';
 142                 N = 4;/*FIXME find next valid byte*/
 143         }
 144
 145         *u = (a[0]<<24) | (a[1]<<16) | (a[2]<<8) | a[3];
 146         return N;
 147 }
 148
 149
 150
 151 void tree_insert(
 152         struct treenode* root,
 153         int (*compare)(void* k1, void* k2),
 154         void* key, void* value)
 155 {
 156
 157         struct treenode* node = xmalloc(sizeof(struct treenode));
 158         struct treenode* ptr;
 159         node->key = key;
 160         node->value = value;
 161         node->l = NULL;
 162         node->r = NULL;
 163
 164         ptr = root;
 165         while(1){
 166                 if( compare(ptr->key, key) < 0 ){
 167                         if(ptr->l){ptr = ptr->l;}
 168                         else{ptr->l = node; break;}
 169                 }
 170                 else if( compare(ptr->key, key) > 0){
 171                         if(ptr->r){ptr = ptr->r;}
 172                         else{ptr->r = node; break;}
 173                 }
 174                 else{ /* key already exists */
 175                         report_error("tree_insert: key already exists\n");
 176                         break;
 177                 }
 178         }
 179 }
 180
 181 void* tree_search(
 182         struct treenode* root,
 183         int (*compare)(void* k1, void* k2),
 184         void* key)
 185 {
 186         if(root==NULL){
 187                 return NULL;
 188         }
 189         else if(compare(root->key, key)>0){
 190                 return tree_search(root->r, compare, key);
 191         }
 192         else if(compare(root->key, key)<0){
 193                 return tree_search(root->l, compare, key);
 194         }
 195         else{
 196                 return root->value;
 197         }
 198 }
 199
 200
 201
 202 /* rng utility functions */
 203 void rand_reset(unsigned s){
 204         zsrand(s);
 205 }
 206
 207 int randi(int a, int b){
 208         int L = b-a;
 209         int P = 1;
 210         int x;
 211
 212         while(P < L){
 213                 P <<= 1;
 214         }
 215
 216         do{
 217                 x = zrand() & (P-1);
 218         } while(x > L);
 219
 220         return x+a;
 221 }
 222
 223 double randf(){
 224         double D = UINT_MAX;
 225         unsigned x = zrand();
 226         return x / D;
 227 }
 228
 229
 230 /* Copyright 300BC Euclid */
 231 int gcd(int a, int b){
 232         while(b){
 233                 int t = b;
 234                 b = a % b;
 235                 a = t;
 236         }
 237         return a;
 238 }