kernel/dict.c

   1 /*
   2  * tag: dict management
   3  *
   4  * Copyright (C) 2003-2005 Stefan Reinauer, Patrick Mauritz
   5  *
   6  * See the file "COPYING" for further information about
   7  * the copyright and warranty status of this work.
   8  */
   9
  10 #include "config.h"
  11 #include "kernel/kernel.h"
  12 #include "dict.h"
  13 #ifdef BOOTSTRAP
  14 #include <string.h>
  15 #else
  16 #include "libc/string.h"
  17 #endif
  18 #include "cross.h"
  19
  20
  21 unsigned char *dict = NULL;
  22 ucell *last;
  23 cell dicthead = 0;
  24 cell dictlimit = 0;
  25
  26 /* lfa2nfa
  27  * converts a link field address to a name field address,
  28  * i.e find pointer to a given words name
  29  */
  30
  31 ucell lfa2nfa(ucell ilfa)
  32 {
  33         /* get offset from dictionary start */
  34         ilfa = ilfa - (ucell)pointer2cell(dict);
  35         ilfa--;                         /* skip status        */
  36         while (dict[--ilfa] == 0);      /* skip all pad bytes */
  37         ilfa -= (dict[ilfa] - 128);
  38         return ilfa + (ucell)pointer2cell(dict);
  39 }
  40
  41 /* lfa2cfa
  42  * converts a link field address to a code field address.
  43  * in this forth implementation this is just a fixed offset
  44  */
  45
  46 static xt_t lfa2cfa(ucell ilfa)
  47 {
  48         return (xt_t)(ilfa + sizeof(cell));
  49 }
  50
  51
  52 /* fstrlen - returns length of a forth string. */
  53
  54 ucell fstrlen(ucell fstr)
  55 {
  56         fstr -= pointer2cell(dict)+1;
  57         //fstr -= pointer2cell(dict); FIXME
  58         while (dict[++fstr] < 128)
  59                 ;
  60         return dict[fstr] - 128;
  61 }
  62
  63 /* to_lower - convert a character to lowecase */
  64
  65 static int to_lower(int c)
  66 {
  67         return ((c >= 'A') && (c <= 'Z')) ? (c - 'A' + 'a') : c;
  68 }
  69
  70 /* fstrcmp - compare null terminated string with forth string. */
  71
  72 static int fstrcmp(const char *s1, ucell fstr)
  73 {
  74         char *s2 = (char*)cell2pointer(fstr);
  75         while (*s1) {
  76                 if ( to_lower(*(s1++)) != to_lower(*(s2++)) )
  77                         return -1;
  78         }
  79         return 0;
  80 }
  81
  82 /* fstrncpy - copy a forth string to a destination (with NULL termination) */
  83
  84 void fstrncpy(char *dest, ucell src, unsigned int maxlen)
  85 {
  86         int len = fstrlen(src);
  87
  88         if (fstrlen(src) >= maxlen) len = maxlen - 1;
  89         memcpy(dest, cell2pointer(src), len);
  90         *(dest + len) = '\0';
  91 }
  92
  93
  94 /* findword
  95  * looks up a given word in the dictionary. This function
  96  * is used by the c based interpreter and to find the "initialize"
  97  * word.
  98  */
  99
 100 xt_t findword(const char *s1)
 101 {
 102         ucell tmplfa, len;
 103
 104         if (!last)
 105                 return 0;
 106
 107         tmplfa = read_ucell(last);
 108
 109         len = strlen(s1);
 110
 111         while (tmplfa) {
 112                 ucell nfa = lfa2nfa(tmplfa);
 113
 114                 if (len == fstrlen(nfa) && !fstrcmp(s1, nfa)) {
 115                         return lfa2cfa(tmplfa);
 116                 }
 117
 118                 tmplfa = read_ucell(cell2pointer(tmplfa));
 119         }
 120
 121         return 0;
 122 }
 123
 124
 125 /* findsemis_wordlist
 126  * Given a DOCOL xt and a wordlist, find the address of the semis
 127  * word at the end of the word definition. We do this by finding
 128  * the word before this in the dictionary, then counting back one
 129  * from the NFA.
 130  */
 131
 132 static ucell findsemis_wordlist(ucell xt, ucell wordlist)
 133 {
 134         ucell tmplfa, nextlfa, nextcfa;
 135
 136         if (!wordlist)
 137                 return 0;
 138
 139         tmplfa = read_ucell(cell2pointer(wordlist));
 140         nextcfa = lfa2cfa(tmplfa);
 141
 142         /* Catch the special case where the lfa of the word we
 143          * want is the last word in the dictionary; in that case
 144          * the end of the word is given by "here" - 1 */
 145         if (nextcfa == xt)
 146                 return pointer2cell(dict) + dicthead - sizeof(cell);
 147
 148         while (tmplfa) {
 149
 150                 /* Peek ahead and see if the next CFA in the list is the
 151                  * one we are searching for */
 152                 nextlfa = read_ucell(cell2pointer(tmplfa));
 153                 nextcfa = lfa2cfa(nextlfa);
 154
 155                 /* If so, count back 1 cell from the current NFA */
 156                 if (nextcfa == xt)
 157                         return lfa2nfa(tmplfa) - sizeof(cell);
 158
 159                 tmplfa = nextlfa;
 160         }
 161
 162         return 0;
 163 }
 164
 165
 166 /* findsemis
 167  * Given a DOCOL xt, find the address of the semis word at the end
 168  * of the word definition by searching all vocabularies */
 169
 170 ucell findsemis(ucell xt)
 171 {
 172         ucell usesvocab = findword("vocabularies?") + sizeof(cell);
 173         unsigned int i;
 174
 175         if (read_ucell(cell2pointer(usesvocab))) {
 176                 /* Vocabularies are in use, so search each one in turn */
 177                 ucell numvocabs = findword("#order") + sizeof(cell);
 178
 179                 for (i = 0; i < read_ucell(cell2pointer(numvocabs)); i++) {
 180                         ucell vocabs = findword("vocabularies") + 2 * sizeof(cell);
 181                         ucell semis = findsemis_wordlist(xt, read_cell(cell2pointer(vocabs + (i * sizeof(cell)))));
 182
 183                         /* If we get a non-zero result, we found the xt in this vocab */
 184                         if (semis)
 185                                 return semis;
 186                 }
 187         } else {
 188                 /* Vocabularies not in use */
 189                 return findsemis_wordlist(xt, read_ucell(last));
 190         }
 191
 192         return 0;
 193 }
 194
 195
 196 /* findxtfromcell_wordlist
 197  * Given a cell and a wordlist, determine the CFA of the word containing
 198  * the cell or 0 if we are unable to return a suitable CFA
 199  */
 200
 201 ucell findxtfromcell_wordlist(ucell incell, ucell wordlist)
 202 {
 203         ucell tmplfa;
 204
 205         if (!wordlist)
 206                 return 0;
 207
 208         tmplfa = read_ucell(cell2pointer(wordlist));
 209         while (tmplfa) {
 210                 if (tmplfa < incell)
 211                         return lfa2cfa(tmplfa);
 212
 213                 tmplfa = read_ucell(cell2pointer(tmplfa));
 214         }
 215
 216         return 0;
 217 }
 218
 219
 220 /* findxtfromcell
 221  * Given a cell, determine the CFA of the word containing
 222  * the cell by searching all vocabularies
 223  */
 224
 225 ucell findxtfromcell(ucell incell)
 226 {
 227         ucell usesvocab = findword("vocabularies?") + sizeof(cell);
 228         unsigned int i;
 229
 230         if (read_ucell(cell2pointer(usesvocab))) {
 231                 /* Vocabularies are in use, so search each one in turn */
 232                 ucell numvocabs = findword("#order") + sizeof(cell);
 233
 234                 for (i = 0; i < read_ucell(cell2pointer(numvocabs)); i++) {
 235                         ucell vocabs = findword("vocabularies") + 2 * sizeof(cell);
 236                         ucell semis = findxtfromcell_wordlist(incell, read_cell(cell2pointer(vocabs + (i * sizeof(cell)))));
 237
 238                         /* If we get a non-zero result, we found the xt in this vocab */
 239                         if (semis)
 240                                 return semis;
 241                 }
 242         } else {
 243                 /* Vocabularies not in use */
 244                 return findxtfromcell_wordlist(incell, read_ucell(last));
 245         }
 246
 247         return 0;
 248 }
 249
 250 void dump_header(dictionary_header_t *header)
 251 {
 252         printk("OpenBIOS dictionary:\n");
 253         printk("  version:     %d\n", header->version);
 254         printk("  cellsize:    %d\n", header->cellsize);
 255         printk("  endianess:   %s\n", header->endianess?"big":"little");
 256         printk("  compression: %s\n", header->compression?"yes":"no");
 257         printk("  relocation:  %s\n", header->relocation?"yes":"no");
 258         printk("  checksum:    %08x\n", target_long(header->checksum));
 259         printk("  length:      %08x\n", target_long(header->length));
 260         printk("  last:        %0" FMT_CELL_x "\n", target_cell(header->last));
 261 }
 262
 263 ucell load_dictionary(const char *data, ucell len)
 264 {
 265         u32 checksum=0;
 266         const char *checksum_walk;
 267         ucell *walk, *reloc_table;
 268         dictionary_header_t *header=(dictionary_header_t *)data;
 269
 270         /* assertions */
 271         if (len <= (sizeof(dictionary_header_t)) || strncmp(DICTID, data, 8))
 272                 return 0;
 273 #ifdef CONFIG_DEBUG_DICTIONARY
 274         dump_header(header);
 275 #endif
 276
 277         checksum_walk=data;
 278         while (checksum_walk<data+len) {
 279                 checksum+=read_long(checksum_walk);
 280                 checksum_walk+=sizeof(u32);
 281         }
 282
 283         if(checksum) {
 284                 printk("Checksum invalid (%08x)!\n", checksum);
 285                 return 0;
 286         }
 287
 288         data += sizeof(dictionary_header_t);
 289
 290         dicthead = target_long(header->length);
 291
 292         memcpy(dict, data, dicthead);
 293         reloc_table=(ucell *)(data+dicthead);
 294
 295 #ifdef CONFIG_DEBUG_DICTIONARY
 296         printk("\nmoving dictionary (%x bytes) to %x\n",
 297                         (ucell)dicthead, (ucell)dict);
 298         printk("\ndynamic relocation...");
 299 #endif
 300
 301         for (walk = (ucell *) dict; walk < (ucell *) (dict + dicthead);
 302              walk++) {
 303                 int pos, bit, l;
 304                 l=(walk-(ucell *)dict);
 305                 pos=l/BITS;
 306                 bit=l&~(-BITS);
 307                 if (reloc_table[pos] & target_ucell((ucell)1ULL << bit)) {
 308                         // printk("%lx, pos %x, bit %d\n",*walk, pos, bit);
 309                         write_ucell(walk, read_ucell(walk)+pointer2cell(dict));
 310                 }
 311         }
 312
 313 #ifdef CONFIG_DEBUG_DICTIONARY
 314         printk(" done.\n");
 315 #endif
 316
 317         last = (ucell *)(dict + target_ucell(header->last));
 318
 319         return -1;
 320 }