- added new_hash2 (faster & better distrib. hash)
[sip-router] / parser / parse_hname2.c
1 /*
2  * $Id$
3  *
4  * Copyright (C) 2001-2003 Fhg Fokus
5  *
6  * This file is part of ser, a free SIP server.
7  *
8  * ser is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU General Public License as published by
10  * the Free Software Foundation; either version 2 of the License, or
11  * (at your option) any later version
12  *
13  * For a license to use the ser software under conditions
14  * other than those described here, or to purchase support for this
15  * software, please contact iptel.org by e-mail at the following addresses:
16  *    info@iptel.org
17  *
18  * ser is distributed in the hope that it will be useful,
19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
21  * GNU General Public License for more details.
22  *
23  * You should have received a copy of the GNU General Public License 
24  * along with this program; if not, write to the Free Software 
25  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
26  */
27
28
29
30 #include "parse_hname2.h"
31 #include "keys.h"
32 #include "../ut.h"  /* q_memchr */
33
34 /*
35  * Size of hash table, this is magic value
36  * that ensures, that there are no synonyms for
37  * frequently used keys (frequently used keys are
38  * 4-byte parts of message headers we recognize)
39  * WARNING ! This value MUST be recalculated if you want
40  * a new header to be recognized
41  */
42 #define HASH_TABLE_SIZE 9349
43
44
45 /*
46  * Hash function
47  */
48 #define HASH_FUNC(val) ((val) % HASH_TABLE_SIZE)
49
50
51 /*
52  * This constants marks empty hash table element
53  */
54 #define HASH_EMPTY 0x2d2d2d2d
55
56
57 /*
58  * Hash table entry
59  */
60 struct ht_entry {
61         unsigned int key;
62         unsigned int value;
63 };
64
65
66 static struct ht_entry hash_table[HASH_TABLE_SIZE];
67
68
69 /*
70  * Pointer to the hash table
71  */
72 /*
73 static struct ht_entry *hash_table;
74 */
75
76
77 /*
78  * Declarations
79  */
80 static inline char* skip_ws     (char* p, unsigned int size);
81 void                init_htable (void);
82 static void         set_entry   (unsigned int key, unsigned int val);
83 static inline int   unify       (int key);
84
85
86 /*
87  * Skip all whitechars and return position of the first
88  * non-white char
89  */
90 static inline char* skip_ws(char* p, unsigned int size)
91 {
92         char* end;
93         
94         end = p + size;
95         for(; p < end; p++) {
96                 if ((*p != ' ') && (*p != '\t')) return p;
97         }
98         return p;
99 }
100         
101
102 /*
103  * Used to initialize hash table
104  */
105 static void set_entry(unsigned int key, unsigned int val)
106 {
107         hash_table[HASH_FUNC(key)].key = key;
108         hash_table[HASH_FUNC(key)].value = val;
109 }
110
111
112 /*
113  * cSeQ -> CSeq and so on...
114  */ 
115 static inline int unify(int key)
116 {
117         register struct ht_entry* en;
118
119         en = &hash_table[HASH_FUNC(key)];
120         if (en->key == key) {
121                 return en->value;
122         } else {
123                 return key;
124         }
125 }
126
127
128 /*
129  * Parser macros
130  */
131 #include "case_via.h"      /* Via */
132 #include "case_from.h"     /* From */
133 #include "case_to.h"       /* To */
134 #include "case_cseq.h"     /* CSeq */
135 #include "case_call.h"     /* Call-ID */
136 #include "case_cont.h"     /* Contact, Content-Type, Content-Length */
137 #include "case_rout.h"     /* Route */
138 #include "case_max.h"      /* Max-Forwards */
139 #include "case_reco.h"     /* Record-Route */
140 #include "case_auth.h"     /* Authorization */
141 #include "case_expi.h"     /* Expires */
142 #include "case_prox.h"     /* Proxy-Authorization, Proxy-Require */
143 #include "case_allo.h"     /* Allow */
144 #include "case_unsu.h"     /* Unsupported */
145 #include "case_requ.h"     /* Require */
146 #include "case_supp.h"     /* Supported */
147 #include "case_www.h"      /* WWW-Authenticate */
148 #include "case_even.h"     /* Event */
149
150
151 #define READ(val) \
152 (*(val + 0) + (*(val + 1) << 8) + (*(val + 2) << 16) + (*(val + 3) << 24))
153
154
155 #define FIRST_QUATERNIONS       \
156         case _Via1_: Via1_CASE; \
157         case _From_: From_CASE; \
158         case _To12_: To12_CASE; \
159         case _CSeq_: CSeq_CASE; \
160         case _Call_: Call_CASE; \
161         case _Cont_: Cont_CASE; \
162         case _Rout_: Rout_CASE; \
163         case _Max__: Max_CASE;  \
164         case _Reco_: Reco_CASE; \
165         case _Via2_: Via2_CASE; \
166         case _Auth_: Auth_CASE; \
167         case _Expi_: Expi_CASE; \
168         case _Prox_: Prox_CASE; \
169         case _Allo_: Allo_CASE; \
170         case _Unsu_: Unsu_CASE; \
171         case _Requ_: Requ_CASE; \
172         case _Supp_: Supp_CASE; \
173         case _WWW__: WWW_CASE;  \
174         case _Even_: Even_CASE;
175
176
177 #define PARSE_COMPACT(id)          \
178         switch(*(p + 1)) {         \
179         case ' ':                  \
180                 hdr->type = id;    \
181                 p += 2;            \
182                 goto dc_end;       \
183                                    \
184         case ':':                  \
185                 hdr->type = id;    \
186                 hdr->name.len = 1; \
187                 *(p + 1) = '\0';   \
188                 return (p + 2);    \
189         }                            
190
191
192 char* parse_hname2(char* begin, char* end, struct hdr_field* hdr)
193 {
194         register char* p;
195         register int val;
196
197         if ((end - begin) < 4) {
198                 hdr->type = HDR_ERROR;
199                 return begin;
200         }
201
202         p = begin;
203         val = READ(p);
204         hdr->name.s = begin;
205
206
207         switch(val) {
208         FIRST_QUATERNIONS;
209
210         default:
211                 switch(*p) {
212                 case 'T':                           
213                 case 't':                           
214                         switch(*(p + 1)) {          
215                         case 'o':                   
216                         case 'O':                   
217                         case ' ':                   
218                                 hdr->type = HDR_TO; 
219                                 p += 2;             
220                                 goto dc_end;        
221                                 
222                         case ':':                   
223                                 hdr->type = HDR_TO; 
224                                 hdr->name.len = 1;  
225                                 *(p + 1) = '\0'; 
226                                 return (p + 2);     
227                         }                           
228                         break;
229
230                 case 'V':                            
231                 case 'v':                            
232                         PARSE_COMPACT(HDR_VIA);
233                         break;
234                         
235                 case 'F':
236                 case 'f':
237                         PARSE_COMPACT(HDR_FROM);
238                         break;
239                         
240                 case 'I':
241                 case 'i':
242                         PARSE_COMPACT(HDR_CALLID);
243                         break;
244
245                 case 'M':
246                 case 'm':
247                         PARSE_COMPACT(HDR_CONTACT);
248                         break;
249
250                 case 'L':
251                 case 'l':
252                         PARSE_COMPACT(HDR_CONTENTLENGTH);
253                         break;
254
255                 case 'C':
256                 case 'c':
257                         PARSE_COMPACT(HDR_CONTENTTYPE);
258                         break;
259
260                 case 'K':
261                 case 'k':
262                         PARSE_COMPACT(HDR_SUPPORTED);
263                         break;
264
265                 case 'O':
266                 case 'o':
267                         PARSE_COMPACT(HDR_EVENT);
268                         break;
269                 }
270                 
271                 val = unify(val);
272                 switch(val) {
273                 FIRST_QUATERNIONS;
274                 default: goto other;
275                 }
276         }
277
278              /* Double colon hasn't been found yet */
279  dc_end:
280         p = skip_ws(p, end - p);
281         if (*p != ':') {   
282                 goto other;
283         } else {
284                 hdr->name.len = p - hdr->name.s;
285                 *p = '\0';
286                 return (p + 1);
287         }
288
289              /* Unknown header type */
290  other:    
291         p = q_memchr(p, ':', end - p);
292         if (!p) {        /* No double colon found, error.. */
293                 hdr->type = HDR_ERROR;
294                 hdr->name.s = 0;
295                 hdr->name.len = 0;
296                 return 0;
297         } else {
298                 hdr->type = HDR_OTHER;
299                 *p = '\0';
300                 hdr->name.len = p - hdr->name.s;
301                 return (p + 1);
302         }
303 }
304
305
306 /* Number of distinct keys */
307 #define NUM_KEYS  608
308
309 /* Number of distinct values */
310 #define NUM_VALS 50
311
312
313 /*
314  * Create synonym-less (precalculated) hash table
315  */
316 void init_hfname_parser(void)
317 {
318         int i, j, k;
319
320              /* Hash table values */
321         unsigned int init_val[NUM_VALS] = {
322                 _Allo_, _Auth_, _oriz_, _atio_, _Call_, __ID2_, __ID1_, _Cont_,
323                 _act2_, _act1_, _ent__, _Leng_, _th12_, _Type_, _CSeq_, _Expi_,
324                 _res2_, _res1_, _From_, _Max__, _Forw_, _ards_, _Prox_, _y_Au_,
325                 _thor_, _izat_, _ion2_, _ion1_, _y_Re_, _quir_, _Reco_, _rd_R_,
326                 _oute_, _Requ_, _ire2_, _ire1_, _Rout_, _Supp_, _orte_, _To12_,
327                 _Unsu_, _ppor_, _ted2_, _ted1_, _Via2_, _Via1_, _WWW__, _enti_,
328                 _cate_, _Even_
329         };
330
331              /* Number of keys associated to each value */
332         unsigned int key_nums[NUM_VALS] = {
333                 16, 16, 16, 16, 16,  4,  4, 16, 
334                  8,  8,  8, 16,  4, 16, 16, 16, 
335                  8,  8, 16,  8, 16, 16, 16,  8, 
336                 16, 16,  8,  8,  8, 16, 16,  8, 
337                 16, 16,  8,  8, 16, 16, 16,  4, 
338                 16, 16,  8,  8,  8,  8,  8, 16,
339                 16, 16
340         };
341
342              /* Hash table keys */
343         unsigned int init_key[NUM_KEYS] = {
344                 _allo_, _allO_, _alLo_, _alLO_, _aLlo_, _aLlO_, _aLLo_, _aLLO_, 
345                 _Allo_, _AllO_, _AlLo_, _AlLO_, _ALlo_, _ALlO_, _ALLo_, _ALLO_, 
346                 _auth_, _autH_, _auTh_, _auTH_, _aUth_, _aUtH_, _aUTh_, _aUTH_, 
347                 _Auth_, _AutH_, _AuTh_, _AuTH_, _AUth_, _AUtH_, _AUTh_, _AUTH_, 
348                 _oriz_, _oriZ_, _orIz_, _orIZ_, _oRiz_, _oRiZ_, _oRIz_, _oRIZ_, 
349                 _Oriz_, _OriZ_, _OrIz_, _OrIZ_, _ORiz_, _ORiZ_, _ORIz_, _ORIZ_, 
350                 _atio_, _atiO_, _atIo_, _atIO_, _aTio_, _aTiO_, _aTIo_, _aTIO_, 
351                 _Atio_, _AtiO_, _AtIo_, _AtIO_, _ATio_, _ATiO_, _ATIo_, _ATIO_, 
352                 _call_, _calL_, _caLl_, _caLL_, _cAll_, _cAlL_, _cALl_, _cALL_, 
353                 _Call_, _CalL_, _CaLl_, _CaLL_, _CAll_, _CAlL_, _CALl_, _CALL_, 
354                 __id2_, __iD2_, __Id2_, __ID2_, __id1_, __iD1_, __Id1_, __ID1_, 
355                 _cont_, _conT_, _coNt_, _coNT_, _cOnt_, _cOnT_, _cONt_, _cONT_, 
356                 _Cont_, _ConT_, _CoNt_, _CoNT_, _COnt_, _COnT_, _CONt_, _CONT_, 
357                 _act2_, _acT2_, _aCt2_, _aCT2_, _Act2_, _AcT2_, _ACt2_, _ACT2_, 
358                 _act1_, _acT1_, _aCt1_, _aCT1_, _Act1_, _AcT1_, _ACt1_, _ACT1_, 
359                 _ent__, _enT__, _eNt__, _eNT__, _Ent__, _EnT__, _ENt__, _ENT__, 
360                 _leng_, _lenG_, _leNg_, _leNG_, _lEng_, _lEnG_, _lENg_, _lENG_, 
361                 _Leng_, _LenG_, _LeNg_, _LeNG_, _LEng_, _LEnG_, _LENg_, _LENG_, 
362                 _th12_, _tH12_, _Th12_, _TH12_, _type_, _typE_, _tyPe_, _tyPE_, 
363                 _tYpe_, _tYpE_, _tYPe_, _tYPE_, _Type_, _TypE_, _TyPe_, _TyPE_, 
364                 _TYpe_, _TYpE_, _TYPe_, _TYPE_, _cseq_, _cseQ_, _csEq_, _csEQ_, 
365                 _cSeq_, _cSeQ_, _cSEq_, _cSEQ_, _Cseq_, _CseQ_, _CsEq_, _CsEQ_, 
366                 _CSeq_, _CSeQ_, _CSEq_, _CSEQ_, _expi_, _expI_, _exPi_, _exPI_, 
367                 _eXpi_, _eXpI_, _eXPi_, _eXPI_, _Expi_, _ExpI_, _ExPi_, _ExPI_, 
368                 _EXpi_, _EXpI_, _EXPi_, _EXPI_, _res2_, _reS2_, _rEs2_, _rES2_, 
369                 _Res2_, _ReS2_, _REs2_, _RES2_, _res1_, _reS1_, _rEs1_, _rES1_, 
370                 _Res1_, _ReS1_, _REs1_, _RES1_, _from_, _froM_, _frOm_, _frOM_, 
371                 _fRom_, _fRoM_, _fROm_, _fROM_, _From_, _FroM_, _FrOm_, _FrOM_, 
372                 _FRom_, _FRoM_, _FROm_, _FROM_, _max__, _maX__, _mAx__, _mAX__, 
373                 _Max__, _MaX__, _MAx__, _MAX__, _forw_, _forW_, _foRw_, _foRW_, 
374                 _fOrw_, _fOrW_, _fORw_, _fORW_, _Forw_, _ForW_, _FoRw_, _FoRW_, 
375                 _FOrw_, _FOrW_, _FORw_, _FORW_, _ards_, _ardS_, _arDs_, _arDS_, 
376                 _aRds_, _aRdS_, _aRDs_, _aRDS_, _Ards_, _ArdS_, _ArDs_, _ArDS_, 
377                 _ARds_, _ARdS_, _ARDs_, _ARDS_, _prox_, _proX_, _prOx_, _prOX_, 
378                 _pRox_, _pRoX_, _pROx_, _pROX_, _Prox_, _ProX_, _PrOx_, _PrOX_, 
379                 _PRox_, _PRoX_, _PROx_, _PROX_, _y_au_, _y_aU_, _y_Au_, _y_AU_, 
380                 _Y_au_, _Y_aU_, _Y_Au_, _Y_AU_, _thor_, _thoR_, _thOr_, _thOR_, 
381                 _tHor_, _tHoR_, _tHOr_, _tHOR_, _Thor_, _ThoR_, _ThOr_, _ThOR_, 
382                 _THor_, _THoR_, _THOr_, _THOR_, _izat_, _izaT_, _izAt_, _izAT_, 
383                 _iZat_, _iZaT_, _iZAt_, _iZAT_, _Izat_, _IzaT_, _IzAt_, _IzAT_, 
384                 _IZat_, _IZaT_, _IZAt_, _IZAT_, _ion2_, _ioN2_, _iOn2_, _iON2_, 
385                 _Ion2_, _IoN2_, _IOn2_, _ION2_, _ion1_, _ioN1_, _iOn1_, _iON1_, 
386                 _Ion1_, _IoN1_, _IOn1_, _ION1_, _y_re_, _y_rE_, _y_Re_, _y_RE_, 
387                 _Y_re_, _Y_rE_, _Y_Re_, _Y_RE_, _quir_, _quiR_, _quIr_, _quIR_, 
388                 _qUir_, _qUiR_, _qUIr_, _qUIR_, _Quir_, _QuiR_, _QuIr_, _QuIR_, 
389                 _QUir_, _QUiR_, _QUIr_, _QUIR_, _reco_, _recO_, _reCo_, _reCO_, 
390                 _rEco_, _rEcO_, _rECo_, _rECO_, _Reco_, _RecO_, _ReCo_, _ReCO_, 
391                 _REco_, _REcO_, _RECo_, _RECO_, _rd_r_, _rd_R_, _rD_r_, _rD_R_, 
392                 _Rd_r_, _Rd_R_, _RD_r_, _RD_R_, _oute_, _outE_, _ouTe_, _ouTE_, 
393                 _oUte_, _oUtE_, _oUTe_, _oUTE_, _Oute_, _OutE_, _OuTe_, _OuTE_, 
394                 _OUte_, _OUtE_, _OUTe_, _OUTE_, _requ_, _reqU_, _reQu_, _reQU_, 
395                 _rEqu_, _rEqU_, _rEQu_, _rEQU_, _Requ_, _ReqU_, _ReQu_, _ReQU_, 
396                 _REqu_, _REqU_, _REQu_, _REQU_, _ire2_, _irE2_, _iRe2_, _iRE2_, 
397                 _Ire2_, _IrE2_, _IRe2_, _IRE2_, _ire1_, _irE1_, _iRe1_, _iRE1_, 
398                 _Ire1_, _IrE1_, _IRe1_, _IRE1_, _rout_, _rouT_, _roUt_, _roUT_, 
399                 _rOut_, _rOuT_, _rOUt_, _rOUT_, _Rout_, _RouT_, _RoUt_, _RoUT_, 
400                 _ROut_, _ROuT_, _ROUt_, _ROUT_, _supp_, _supP_, _suPp_, _suPP_, 
401                 _sUpp_, _sUpP_, _sUPp_, _sUPP_, _Supp_, _SupP_, _SuPp_, _SuPP_, 
402                 _SUpp_, _SUpP_, _SUPp_, _SUPP_, _orte_, _ortE_, _orTe_, _orTE_, 
403                 _oRte_, _oRtE_, _oRTe_, _oRTE_, _Orte_, _OrtE_, _OrTe_, _OrTE_, 
404                 _ORte_, _ORtE_, _ORTe_, _ORTE_, _to12_, _tO12_, _To12_, _TO12_, 
405                 _unsu_, _unsU_, _unSu_, _unSU_, _uNsu_, _uNsU_, _uNSu_, _uNSU_, 
406                 _Unsu_, _UnsU_, _UnSu_, _UnSU_, _UNsu_, _UNsU_, _UNSu_, _UNSU_, 
407                 _ppor_, _ppoR_, _ppOr_, _ppOR_, _pPor_, _pPoR_, _pPOr_, _pPOR_, 
408                 _Ppor_, _PpoR_, _PpOr_, _PpOR_, _PPor_, _PPoR_, _PPOr_, _PPOR_, 
409                 _ted2_, _teD2_, _tEd2_, _tED2_, _Ted2_, _TeD2_, _TEd2_, _TED2_, 
410                 _ted1_, _teD1_, _tEd1_, _tED1_, _Ted1_, _TeD1_, _TEd1_, _TED1_, 
411                 _via2_, _viA2_, _vIa2_, _vIA2_, _Via2_, _ViA2_, _VIa2_, _VIA2_, 
412                 _via1_, _viA1_, _vIa1_, _vIA1_, _Via1_, _ViA1_, _VIa1_, _VIA1_, 
413                 _www__, _wwW__, _wWw__, _wWW__, _Www__, _WwW__, _WWw__, _WWW__, 
414                 _enti_, _entI_, _enTi_, _enTI_, _eNti_, _eNtI_, _eNTi_, _eNTI_, 
415                 _Enti_, _EntI_, _EnTi_, _EnTI_, _ENti_, _ENtI_, _ENTi_, _ENTI_, 
416                 _cate_, _catE_, _caTe_, _caTE_, _cAte_, _cAtE_, _cATe_, _cATE_, 
417                 _Cate_, _CatE_, _CaTe_, _CaTE_, _CAte_, _CAtE_, _CATe_, _CATE_,
418                 _even_, _eveN_, _evEn_, _evEN_, _eVen_, _eVeN_, _eVEn_, _eVEN_, 
419                 _Even_, _EveN_, _EvEn_, _EvEN_, _EVen_, _EVeN_, _EVEn_, _EVEN_, 
420         }; 
421
422              /* Mark all elements as empty */
423         for(i = 0; i < HASH_TABLE_SIZE; i++) {
424                 set_entry(HASH_EMPTY, HASH_EMPTY);
425         }
426
427         k = 0;
428
429         for(i = 0; i < NUM_VALS; i++) {
430                 for(j = 0; j < key_nums[i]; j++) {
431                         set_entry(init_key[k++], init_val[i]);
432                 }
433         }
434 }