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 fatal_error(const char* format, ...){
  39         va_list ap;
  40         va_start(ap, format);
  41         report_verror(format, ap);
  42         va_end(ap);
  43         exit(-1);
  44 }
  45
  46 void boot_msg(const char* format, ...){
  47         va_list ap;
  48         va_start(ap, format);
  49         vprintf(format, ap);
  50         va_end(ap);
  51 }
  52
  53 void error_msg(const char* format, ...){
  54         va_list ap;
  55         va_start(ap, format);
  56         report_verror(format, ap);
  57         va_end(ap);
  58 }
  59
  60 void out_of_memory(const char* prefix){
  61         error_msg("%s: *out of memory*\n", prefix);
  62         exit(-2);
  63 }
  64
  65 /* 'safe' functions */
  66 void* xmalloc(size_t size){
  67         void* v = malloc(size);
  68         if(!v){
  69                 /* On Linux malloc by default does not return NULL
  70                 even if there is no more memory. So this function
  71                 isn't really 'safe' on that system. */
  72                 out_of_memory("xmalloc");
  73         }
  74         return v;
  75 }
  76
  77 char* strxcpy(const char* str){
  78         char* cpy = xmalloc(strlen(str)+1);
  79         strcpy(cpy, str);
  80         return cpy;
  81 }
  82
  83 void strmcat(char* dst, const char* src, size_t n){
  84         strncat(dst, src, n - strlen(src) - 1);
  85 }
  86
  87
  88
  89
  90 /*
  91    decodes utf8 encoded string str and places the
  92    next character in u.
  93    returns the number of bytes of str consumed.
  94 */
  95 int unicode_getc(char* str, utf32* u){
  96         /*unsigned char b[4] = {str[0], str[1], str[2], str[3]};*/
  97         unsigned char b[4];
  98         unsigned char a[4] = {0,0,0,0};
  99         int N;
 100
 101         memcpy(b, str, 4);
 102
 103         /* 1111 0xf
 104            1110 0xe
 105            1100 0xc
 106            1000 0x8 */
 107
 108         if((b[0] & 0x80) == 0){ /*one byte sequence*/
 109                 a[3] = b[0];
 110                 N = 1;
 111         }
 112
 113         else if(
 114                 ((b[0]&0xe0)==0xc0) &&
 115                 ((b[1]&0xc0)==0x80)
 116         ){
 117                 /*two byte sequence*/
 118                 a[3] = ((b[0]&0x03)<<6)|(b[1]&0x3f);
 119                 a[2] = (b[0]&0x1c)>>2;
 120                 N = 2;
 121         }
 122
 123         else if(
 124                 ((b[0]&0xf0)==0xe0) &&
 125                 ((b[1]&0xc0)==0x80) &&
 126                 ((b[2]&0xc0)==0x80)
 127         ){
 128                 /*three byte sequence*/
 129                 a[3] = ((b[1]&0x03)<<6)|(b[2]&0x3f);
 130                 a[2] = ((b[0]&0x0f)<<4)|((b[1]&0x3c)>>2);
 131                 N = 3;
 132         }
 133
 134         else if(
 135                 ((b[0]&0xf8)==0xf0) &&
 136                 ((b[1]&0xc0)==0x80) &&
 137                 ((b[2]&0xc0)==0x80) &&
 138                 ((b[3]&0xc0)==0x80)
 139         ){
 140                 /*four byte sequence*/
 141                 a[3] = ((b[2]&0x03)<<6)|(b[3]&0x3f);
 142                 a[2] = ((b[1]&0x0f)<<4)|((b[2]&0x3c)>>2);
 143                 a[1] = ((b[0]&0x03)<<2)|((b[1]&0x30)>>4);
 144                 N = 4;
 145         }
 146
 147         else {
 148                 a[3] = '?';
 149                 N = 4;/*FIXME find next valid byte*/
 150         }
 151
 152         *u = (a[0]<<24) | (a[1]<<16) | (a[2]<<8) | a[3];
 153         return N;
 154 }
 155
 156
 157
 158 void tree_insert(
 159         struct treenode* root,
 160         int (*compare)(void* k1, void* k2),
 161         void* key, void* value)
 162 {
 163
 164         struct treenode* node = xmalloc(sizeof(struct treenode));
 165         struct treenode* ptr;
 166         node->key = key;
 167         node->value = value;
 168         node->l = NULL;
 169         node->r = NULL;
 170
 171         ptr = root;
 172         while(1){
 173                 if( compare(ptr->key, key) < 0 ){
 174                         if(ptr->l){ptr = ptr->l;}
 175                         else{ptr->l = node; break;}
 176                 }
 177                 else if( compare(ptr->key, key) > 0){
 178                         if(ptr->r){ptr = ptr->r;}
 179                         else{ptr->r = node; break;}
 180                 }
 181                 else{ /* key already exists */
 182                         error_msg("tree_insert: key already exists\n");
 183                         break;
 184                 }
 185         }
 186 }
 187
 188 void* tree_search(
 189         struct treenode* root,
 190         int (*compare)(void* k1, void* k2),
 191         void* key)
 192 {
 193         if(root==NULL){
 194                 return NULL;
 195         }
 196         else if(compare(root->key, key)>0){
 197                 return tree_search(root->r, compare, key);
 198         }
 199         else if(compare(root->key, key)<0){
 200                 return tree_search(root->l, compare, key);
 201         }
 202         else{
 203                 return root->value;
 204         }
 205 }
 206
 207
 208
 209 /* rng utility functions */
 210 void rand_reset(unsigned s){
 211         zsrand(s);
 212 }
 213
 214 int randi(int a, int b){
 215         int L = b-a;
 216         int P = 1;
 217         int x;
 218
 219         while(P < L){
 220                 P <<= 1;
 221         }
 222
 223         do{
 224                 x = zrand() & (P-1);
 225         } while(x > L);
 226
 227         return x+a;
 228 }
 229
 230 double randf(){
 231         double D = UINT_MAX;
 232         unsigned x = zrand();
 233         return x / D;
 234 }
 235
 236
 237
 238 char* path_ending(char* path){
 239         char* c = path + strlen(path);
 240         while(*(c-1) != '/' && c > path) c--;
 241         return c;
 242 }
 243
 244
 245 /* Copyright 300BC Euclid */
 246 int gcd(int a, int b){
 247         while(b){
 248                 int t = b;
 249                 b = a % b;
 250                 a = t;
 251         }
 252         return a;
 253 }