446,421 Members | 1,089 Online
Need help? Post your question and get tips & solutions from a community of 446,421 IT Pros & Developers. It's quick & easy.

# Why in hash function use 5381?

 P: n/a i find in many hash function use 5381,for exampla: static constmap_hash hash(char *pchData, int iLen) { unsigned char cBuf; constmap_hash ulHashId; ulHashId = 5381; while (iLen > 0) { cBuf = *pchData++ - 'A'; if (cBuf <= 'Z' - 'A') { cBuf += 'a' - 'A'; } ulHashId = ((ulHashId << 5) + ulHashId) ^ cBuf; --iLen; } return ulHashId; } Can anyone tell me why use 5381 ? thanks!! Nov 14 '05 #1
19 Replies

 P: n/a hr******@sina.com (anguo) writes: i find in many hash function use 5381,for exampla: [...] Can anyone tell me why use 5381 ? This webpage implies that it is a random number selected by Dan Bernstein: . Presumably everyone else just used the same number. -- int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\ \n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\ );while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\ );}return 0;} Nov 14 '05 #2

 P: n/a Ben Pfaff wrote: hr******@sina.com (anguo) writes:i find in many hash function use 5381,for exampla: [...]Can anyone tell me why use 5381 ? This webpage implies that it is a random number selected by Dan Bernstein: . Presumably everyone else just used the same number. Except that it is not so very random looking: 5381 = 012405. This looks like something deeper is involved. The 001/010/100/000/101 raises the question about the choice of the last octal digit, though. -- Martin Ambuhl Nov 14 '05 #3

 P: n/a Ben Pfaff wrote: -- int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\ \n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\ );while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\ );}return 0;} huh "Just another C hacker" :-) Ben.c: (in function main) Ben.c:9:18: Variable i initialized to type arbitrary unsigned integral type, expects int: sizeof(p) / 2 Ben.c:10:9: Function strchr shadows outer declaration An outer declaration is shadowed by the local declaration. Specification of strchr: [function (char *, int) returns char *] Ben.c:11:7: Function putchar shadows outer declaration Specification of putchar: [function (int) returns int] Ben.c:12:10: Test expression for while not boolean, type char: *q Test expression type is not boolean. Ben.c:14:12: Variable strchr used before definition An rvalue is used that may not be initialized to a value on some execution path. Ben.c:17:7: Variable putchar used before definition Ben.c:17:7: Return value (type int) ignored: putchar(p[i]) Result returned by function call is not used. Cheers :) Nov 14 '05 #4

 P: n/a Jean-Michel Collard writes: Ben Pfaff wrote: -- int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\ \n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\ );while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\ );}return 0;} huh "Just another C hacker" :-) [...many warnings snipped...] It's perfectly well-defined, if obfuscated, C. It's not meant to be lint-clean. Based on what I've seen from some versions of lint, a lot of lint warnings are simply nonsensical, so that's not even a good goal for real-world code. Nov 14 '05 #5

 P: n/a Jean-Michel Collard wrote: Ben Pfaff wrote: int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\ \n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\ );while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\ );}return 0;} huh "Just another C hacker" :-) Ben.c: (in function main) Ben.c:9:18: Variable i initialized to type arbitrary unsigned integral type, expects int: sizeof(p) / 2 Correct for this constant value, though. Ben.c:10:9: Function strchr shadows outer declaration An outer declaration is shadowed by the local declaration. Where, pray, is this "outer declaration" to be found? Ben.c:11:7: Function putchar shadows outer declaration And ditto? Ben.c:12:10: Test expression for while not boolean, type char: *q Test expression type is not boolean. Yer_what_? Ben.c:14:12: Variable strchr used before definition An rvalue is used that may not be initialized to a value on some execution path. Ben.c:17:7: Variable putchar used before definition Erm... boggle. Ben.c:17:7: Return value (type int) ignored: putchar(p[i]) Result returned by function call is not used. Gosh. Lint really _is_ prehistoric, isn't it? Richard Nov 14 '05 #6

 P: n/a Richard Bos wrote: Jean-Michel Collard wrote:Ben Pfaff wrote:int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\ \n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\);}return 0;}huh "Just another C hacker" :-)Ben.c: (in function main)Ben.c:9:18: Variable i initialized to type arbitrary unsigned integral type, expects int: sizeof(p) / 2 Correct for this constant value, though. Eh, lint can't tell that. Ben.c:10:9: Function strchr shadows outer declaration An outer declaration is shadowed by the local declaration. Where, pray, is this "outer declaration" to be found? The '#include'd header file? The old-style implicit declaration of everything returning an int? Ben.c:12:10: Test expression for while not boolean, type char: *q Test expression type is not boolean. Yer_what_? Here's where lint is a bit too pedantic (well, here's a single instance out of possibly thousands ;)): C acts like it has a boolean type sometimes, and it certainly has a boolean context. lint doesn't know, and can't be made to know, that things other than boolean-returning relational expressions (such as (a > 5) or (f <= 12)) can meaningfully be used in a boolean context. IMNSHO, lint here goes from pedantic to incorrect. Even the earliest versions of C would gleefully, and conformantly, accept things that aren't strictly booleans where it imposes a boolean context. For lint to complain about such things has never been helpful. Ben.c:14:12: Variable strchr used before definition An rvalue is used that may not be initialized to a value on some execution path.Ben.c:17:7: Variable putchar used before definition Erm... boggle. lint's stupid sometimes. Ben.c:17:7: Return value (type int) ignored: putchar(p[i]) Result returned by function call is not used. Gosh. Lint really _is_ prehistoric, isn't it? According to K&R2, putchar() does indeed return an int. I suspect a cast to void would silence lint, but it's hardly worth it, is it? [OT] I use splint, a lint-a-like, myself, and splint gives you the warning, the explanation, and the argument you can pass to splint to make it shut up about the damned warning. I usually invoke splint with no flags once, then with a few to weed out the more egregiously inane whinings. [/OT] Nov 14 '05 #7

 P: n/a August Derleth writes: lint's stupid sometimes. lint is stupid to the point of uselessness. As just one example, at least one variety of lint emits a warning for the following: long x = 0; saying that the initializer is not of the proper type. -- "I'm not here to convince idiots not to be stupid. They won't listen anyway." --Dann Corbit Nov 14 '05 #8

 P: n/a Ben Pfaff wrote: August Derleth writes: lint's stupid sometimes. lint is stupid to the point of uselessness. As just one example, at least one variety of lint emits a warning for the following: long x = 0; saying that the initializer is not of the proper type. I once encountered a *compiler* that complained about float f = 0.0; .... because of the potential loss of precision in the conversion of `double' to `float'. Perhaps the goal of the compiler vendor was "Get Nothing Right!" -- Er*********@sun.com Nov 14 '05 #10

 P: n/a Eric Sosman wrote: I once encountered a *compiler* that complained about float f = 0.0; ... because of the potential loss of precision in the conversion of `double' to `float'. Perhaps the goal of the compiler vendor was "Get Nothing Right!" I'm not sure I wholly disagree with the compiler in this case. Could you explain why you think a warning is so over-the-top here? Best regards, Sidney Nov 14 '05 #11

 P: n/a In article , Sidney Cadot wrote: Eric Sosman wrote: I once encountered a *compiler* that complained about float f = 0.0; ... because of the potential loss of precision in the conversion of `double' to `float'. Perhaps the goal of the compiler vendor was "Get Nothing Right!" I'm not sure I wholly disagree with the compiler in this case. Could you explain why you think a warning is so over-the-top here? It would be a strange implementation where an assignment of the double precision number 0.0 to a variable of type float would produce a loss of precision. Same for 1.0 or 0.5 . If you have an assignment float f = ; then it would be trivial for the compiler to check whether or not (float)constant == (double)constant or not. Then the compiler can either give a warning: "Warning: Loss of precision" or be quiet if there is no loss of precision. Nov 14 '05 #12

 P: n/a Christian Bau wrote: In article , Sidney Cadot wrote: Eric Sosman wrote: I once encountered a *compiler* that complained about float f = 0.0; ... because of the potential loss of precision in the conversion of `double' to `float'. Perhaps the goal of the compiler vendor was "Get Nothing Right!" I'm not sure I wholly disagree with the compiler in this case. Could you explain why you think a warning is so over-the-top here? It would be a strange implementation where an assignment of the double precision number 0.0 to a variable of type float would produce a loss of precision. Same for 1.0 or 0.5 . If you have an assignment float f = ; then it would be trivial for the compiler to check whether or not (float)constant == (double)constant or not. Then the compiler can either give a warning: "Warning: Loss of precision" or be quiet if there is no loss of precision. If the implementation gives warnings based solely on the code, without regard for implementation defined behavior, then you'll have less new warnings when you port the code, assuming that you paid proper heed to the warnings. -- pete Nov 14 '05 #13

 P: n/a Christian Bau wrote: In article , Sidney Cadot wrote:Eric Sosman wrote: I once encountered a *compiler* that complained about float f = 0.0;... because of the potential loss of precision in theconversion of `double' to `float'. Perhaps the goal ofthe compiler vendor was "Get Nothing Right!"I'm not sure I wholly disagree with the compiler in this case.Could you explain why you think a warning is so over-the-top here? It would be a strange implementation where an assignment of the double precision number 0.0 to a variable of type float would produce a loss of precision. Same for 1.0 or 0.5 . Strange yes, but not impossible, as far as I can tell from the standard. I don't think there's a requirement that zero be exactly representable for floats/doubles. Of course, I wholly agree that an FP implementation would be seriously broken if it couldn't do this. If you have an assignment float f = ; then it would be trivial for the compiler to check whether or not (float)constant == (double)constant or not. Then the compiler can either give a warning: "Warning: Loss of precision" or be quiet if there is no loss of precision. Probably the compiler already said "*possible* loss of precision". Having warnings depend on implementation-defined things is perhaps not a good idea. To have a rather more interesting example: float x = 0.1; We would both, I think, consider the warning to be a good idea at least on radix-2 FP machines; however, I think it is also not unreasonable to get a warning on a radix-10 machine (will make porting efforts ever so much easier). Best regards, Sidney Nov 14 '05 #14

 P: n/a August Derleth wrote: Richard Bos wrote: Jean-Michel Collard wrote:Ben Pfaff wrote:int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\ \n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\);}return 0;}huh "Just another C hacker" :-)Ben.c: (in function main)Ben.c:9:18: Variable i initialized to type arbitrary unsigned integral type, expects int: sizeof(p) / 2 Correct for this constant value, though. Eh, lint can't tell that. Of course it can, for exactly the same reason that I can: in that context, p is a non-variable-sized array, which has constant size - 56, to be precise. sizeof p is therefore 56, and sizeof p/2 is 28, and 28 _must_ convert correctly to int. Ben.c:10:9: Function strchr shadows outer declaration An outer declaration is shadowed by the local declaration. Where, pray, is this "outer declaration" to be found? The '#include'd header file? There _is_ no header file in that code. The old-style implicit declaration of everything returning an int? That doesn't exist unless the function is called without an explicit declaration. Which it isn't. Ben.c:12:10: Test expression for while not boolean, type char: *q Test expression type is not boolean. Yer_what_? Here's where lint is a bit too pedantic No, it's talking out of its hat. The control expression of a while loop need not be "boolean" at all, whatever lint, in its poor addled imagination, thinks a "boolean" type is in pre-99 C. C acts like it has a boolean type sometimes, Not unless you're using C99. and it certainly has a boolean context. Yes. And in those contexts, _any_ scalar will suffice - all that is needed is that it can be tested for being-zero-or-not. lint doesn't know, and can't be made to know, that things other than boolean-returning relational expressions (such as (a > 5) or (f <= 12)) can meaningfully be used in a boolean context. In other words, lint is incorrigibly broken. Such uses are perfectly correct in C, and flagging them as wrong is simply not correct. Ben.c:14:12: Variable strchr used before definition An rvalue is used that may not be initialized to a value on some execution path.Ben.c:17:7: Variable putchar used before definition Erm... boggle. lint's stupid sometimes. Understatement of the year award granted on January 2nd already. Ben.c:17:7: Return value (type int) ignored: putchar(p[i]) Result returned by function call is not used. Gosh. Lint really _is_ prehistoric, isn't it? According to K&R2, putchar() does indeed return an int. Yes. And according to the same K&R, there is no need to use the return value of every single expression. I note, for example, that lint does not complain about the various assignment statements, whose results are ignored as well. I suspect a cast to void would silence lint, but it's hardly worth it, is it? My point exactly. I haven't seen lint-shutting-up casts for ages, and it is indeed hardly worth the trouble to deface your code so badly if you can, with much less effort, throw the bloody dinosaur out the window and use a proper error-checking compiler. Richard Nov 14 '05 #15

 P: n/a Sidney Cadot wrote: Eric Sosman wrote: I once encountered a *compiler* that complained about float f = 0.0; ... because of the potential loss of precision in the conversion of `double' to `float'. Perhaps the goal of the compiler vendor was "Get Nothing Right!" I'm not sure I wholly disagree with the compiler in this case. Could you explain why you think a warning is so over-the-top here? I think the warning should be emitted. Consider: #define SOMEVALUE (0) #define BASEVAL ((SOMEVALUE) / 3.0) ..... globs of code .... float f, g; ..... further globs .... f = BASEVAL; /* WARNING TIME */ g = 3 * BASEVAL; /* WARNING TIME */ otherwise the apparently innocent future change of SOMEVALUE may trigger many confusing warnings. -- Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net) Available for consulting/temporary embedded and systems. USE worldnet address! Nov 14 '05 #16

 P: n/a Christian Bau wrote: In article , Sidney Cadot wrote: Eric Sosman wrote: I once encountered a *compiler* that complained about float f = 0.0; ... because of the potential loss of precision in the conversion of `double' to `float'. Perhaps the goal of the compiler vendor was "Get Nothing Right!" I'm not sure I wholly disagree with the compiler in this case. Could you explain why you think a warning is so over-the-top here? It would be a strange implementation where an assignment of the double precision number 0.0 to a variable of type float would produce a loss of precision. Same for 1.0 or 0.5 . If you have an assignment float f = ; then it would be trivial for the compiler to check whether or not (float)constant == (double)constant or not. Then the compiler can either give a warning: "Warning: Loss of precision" or be quiet if there is no loss of precision. I would doubt very much that the compiler checks that the double value can be assigned to float without loss of precision. Simply that assigning double to float might cause it. -- Joe Wright http://www.jw-wright.com "Everything should be made as simple as possible, but not simpler." --- Albert Einstein --- Nov 14 '05 #17

 P: n/a Arthur J. O'Dwyer wrote: On Mon, 5 Jan 2004, August Derleth wrote:Richard Bos wrote:Jean-Michel Collard wrote:Ben.c:12:10: Test expression for while not boolean, type char: *q Test expression type is not boolean.Yer_what_?Here's where lint is a bit too pedantic (well, here's a single instanceout of possibly thousands ;)): C acts like it has a boolean typesometimes, and it certainly has a boolean context. lint doesn't know,and can't be made to know, that things other than boolean-returningrelational expressions (such as (a > 5) or (f <= 12)) can meaningfullybe used in a boolean context.IMNSHO, lint here goes from pedantic to incorrect. Even the earliestversions of C would gleefully, and conformantly, accept things thataren't strictly booleans where it imposes a boolean context. For lint tocomplain about such things has never been helpful. It might be helpful in cases like if (a=b) It would still be wrong, though. See Richard's post for details, but the upshot is that any scalar value can be coerced via a boolean context into a form usable by any of the conditional statements. Insisting on a boolean type, which was quite mythical until C99, is wrong. What lint should do is shut up about 90% of the cases and correctly warn about cases like yours with a correct statement, such as `assignment used where test expected' or some such. The problems are (1) lint uses the word "boolean" like the programmer is supposed to know what it means, and which "types" are "boolean" enough for lint -- but C90 doesn't have boolean types -- and (2) lint should really know about common idioms like 'if (*q)'. It makes a large bit of sense to warn about 'if (a+b)' or the like, for the sake of lint-ness, but lint should know better than to complain in this case. In other words, lint should not be broken. Ben.c:17:7: Return value (type int) ignored: putchar(p[i]) Result returned by function call is not used.Gosh. Lint really _is_ prehistoric, isn't it?According to K&R2, putchar() does indeed return an int. I suspect a castto void would silence lint, but it's hardly worth it, is it? Some old code, and some overly-portable code, does use casts to void. We even get questions about (void)printf here occasionally. I can only assume there's some way to switch off this warning in modern lints; it would get really obnoxious if you tried to lint a big source file. As Richard said, it's not wrong to ignore the value of anything, including a function call. Otherwise, we'd need to wrap a conditional statement around every assignment statement. [OT]I use splint, a lint-a-like, myself, and splint gives you the warning,the explanation, and the argument you can pass to splint to make it shutup about the damned warning. I usually invoke splint with no flags once,then with a few to weed out the more egregiously inane whinings. Excellent. I wish gcc would do this too, for its warnings. It seems like a very nice feature. It's the only way I'll use a lint-like program at all, especially now. Nov 14 '05 #19

 P: n/a Ben Pfaff wrote: August Derleth writes:lint's stupid sometimes. lint is stupid to the point of uselessness. As just one example, at least one variety of lint emits a warning for the following: long x = 0; saying that the initializer is not of the proper type. You could say long x = 0L; Or you could stop using lint. Whichever. (I'd opt for the second, assuming I have a reasonably good compiler.) Nov 14 '05 #20

### This discussion thread is closed

Replies have been disabled for this discussion.