home *** CD-ROM | disk | FTP | other *** search
/ ProfitPress Mega CDROM2 …eeware (MSDOS)(1992)(Eng) / ProfitPress-MegaCDROM2.B6I / GRAPHICS / MISC / PVQUAN15.ZIP / GIFLIB.ZIP / GIF_HASH.C < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-14  |  4.7 KB  |  101 lines
  1. /************************************************************************
  2.  *                                                                      *
  3.  *                  Copyright (c) 1991, Frank van der Hulst             *
  4.  *                          All Rights Reserved                         *
  5.  *                                                                      *
  6.  * Authors:                                                             *
  7.  *          FvdH - Frank van der Hulst (Wellington, NZ)                     *
  8.  *                                                                      *
  9.  * Versions:                                                            *
  10.  *      V1.1 910626 FvdH - QUANT released for DBW_RENDER                *
  11.  *      V1.2 911021 FvdH - QUANT released for PoV Ray                   *
  12.  *                                                                      *
  13.  ************************************************************************/
  14. /************************************************************************
  15. *   "Gif-Lib" - Yet another gif library.                                             *
  16. *                                                                                                 *
  17. * Written by:  Gershon Elber            IBM PC Ver 0.1,    Jun. 1989            *
  18. *************************************************************************
  19. * Module to support the following operations:                                     *
  20. *                                                                                                 *
  21. * 1. InitHashTable - initialize hash table.                                         *
  22. * 2. ClearHashTable - clear the hash table to an empty state.                 *
  23. * 2. InsertHashTable - insert one item into data structure.                     *
  24. * 3. ExistsHashTable - test if item exists in data structure.                 *
  25. *                                                                                                 *
  26. * This module is used to hash the GIF codes during encoding.                 *
  27. *************************************************************************
  28. * History:                                                                                     *
  29. * 14 Jun 89 - Version 1.0 by Gershon Elber.                                         *
  30. *************************************************************************/
  31.  
  32. #ifdef __TURBOC__
  33. #include <mem.h>
  34. #endif
  35.  
  36. #include "gif_hash.h"
  37.  
  38. #define HT_KEY_MASK        0x1FFF                  /* 13bits keys */
  39.  
  40. /* The 32 bits of the long are divided into two parts for the key & code:   */
  41. /* 1. The code is 12 bits as our compression algorithm is limited to 12bits */
  42. /* 2. The key is 12 bits Prefix code + 8 bit new char or 20 bits.        */
  43. #define HT_GET_KEY(l)    (l >> 12)
  44. #define HT_GET_CODE(l)    (l & 0x0FFF)
  45. #define HT_PUT_KEY(l)    (l << 12)
  46. #define HT_PUT_CODE(l)    (l & 0x0FFF)
  47.  
  48. /******************************************************************************
  49. * Routine to generate an HKey for the hashtable out of the given unique key.  *
  50. * The given Key is assumed to be 20 bits as follows: lower 8 bits are the     *
  51. * new postfix character, while the upper 12 bits are the prefix code.          *
  52. * Because the average hit ratio is only 2 (2 hash references per entry),      *
  53. * evaluating more complex keys (such as twin prime keys) does not worth it!   *
  54. ******************************************************************************/
  55. static int KeyItem(unsigned long Item)
  56. {
  57.      return ((int)((Item >> 12) ^ Item)) & HT_KEY_MASK;
  58. }
  59.  
  60.  
  61. /******************************************************************************
  62. * Routine to clear the HashTable to an empty state.                  *
  63. * This part is a little machine depended. Use the commented part otherwise.   *
  64. ******************************************************************************/
  65. void HashTable_Clear(unsigned long *HashTable)
  66. {
  67.      memset(HashTable, 0xFF, HT_SIZE * sizeof(long));
  68. }
  69.  
  70. /******************************************************************************
  71. * Routine to insert a new Item into the HashTable. The data is assumed to be  *
  72. * new one.                                      *
  73. ******************************************************************************/
  74. void HashTable_Insert(unsigned long *HashTable, unsigned long Key, int Code)
  75. {
  76. int HKey = KeyItem(Key);
  77. unsigned long *HTable = HashTable;
  78.  
  79.     while (HT_GET_KEY(HTable[HKey]) != 0xFFFFFL) {
  80.         HKey = (HKey + 1) & HT_KEY_MASK;
  81.     }
  82.     HTable[HKey] = HT_PUT_KEY(Key) | HT_PUT_CODE(Code);
  83. }
  84.  
  85. /******************************************************************************
  86. * Routine to test if given Key exists in HashTable and if so returns its code *
  87. * Returns the Code if key was found, -1 if not.                      *
  88. ******************************************************************************/
  89. int HashTable_Exists(unsigned long *HashTable, unsigned long Key)
  90. {
  91. int HKey = KeyItem(Key);
  92. unsigned long *HTable = HashTable, HTKey;
  93.  
  94.     while ((HTKey = HT_GET_KEY(HTable[HKey])) != 0xFFFFFL) {
  95.         if (Key == HTKey) return (int)HT_GET_CODE(HTable[HKey]);
  96.         HKey = (HKey + 1) & HT_KEY_MASK;
  97.     }
  98.  
  99.     return -1;
  100. }
  101.