472,373 Members | 1,550 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 472,373 software developers and data experts.

my small hashlib - using pythons hash-functions

Hi.

I wrote a small hashlib for C. Because I'm new to hashes I looked at pythons implementation and
reused *some* of the code... or more the mathematical "hash-function", not really the code.

In particular I looked at pythons hash and lookup functions, so I came up with this (see the code
underneath).

So, can this code be considered as derived and do I have to put my code under the GPL? I'd like to
publish it under something less restrictive, like a BSD style license. But if GPL is the only way,
then GPL it is. :)

-panzi
#define PERTURB_SHIFT 5

static ENTRY_T * lookup(CONTAINER_T * table, hash_const_str_t key,
int (*loop_cond)(ENTRY_T * ptr, hash_const_str_t key)) {
register ENTRY_T * entries = table->entries;
register hash_size_t size = table->size;
register hash_size_t pos = hash(key) % size;
register hash_size_t perturb = pos;

register ENTRY_T * ptr = entries + pos;

while(loop_cond(ptr,key)) {
pos = ((pos << 2) + pos + perturb + 1) % size;
perturb >>= PERTURB_SHIFT;

ptr = entries + pos;

#ifdef HASH_COUNT_COLLISIONS
++ table->collisions;
#endif
}

return ptr;
}

hash_t hash(register hash_const_str_t str) {
/* python 2.5's hash function: */
register hash_size_t len;
register hash_t h;

assert(str);

len = strlen(str);
h = *str << 7;

while (*str)
h = (1000003 * h) ^ *str ++;
h ^= len;

return h;
}
Nov 25 '06 #1
5 2051
Mathias Panzenboeck <e0******@student.tuwien.ac.atwrites:
So, can this code be considered as derived and do I have to put my
code under the GPL? I'd like to publish it under something less
restrictive, like a BSD style license. But if GPL is the only way,
then GPL it is. :)
Python is not GPL'd but has its own license. You can make the derived
work GPL if you want, but it is not required. You'll have to check
its terms to see whether you can specifically use the BSD license.
Simplest might be to just stay with the Python license.
Nov 25 '06 #2
Paul Rubin wrote:
Mathias Panzenboeck <e0******@student.tuwien.ac.atwrites:
>So, can this code be considered as derived and do I have to put my
code under the GPL? I'd like to publish it under something less
restrictive, like a BSD style license. But if GPL is the only way,
then GPL it is. :)

Python is not GPL'd but has its own license. You can make the derived
work GPL if you want, but it is not required. You'll have to check
its terms to see whether you can specifically use the BSD license.
Simplest might be to just stay with the Python license.
Yes, right. It's PSF.

But the question is: *IS* this derived work? I mean, it's not copied code.
It's the same hashing-logic, which I learned by watching pythons code.

-panzi
Nov 25 '06 #3
Mathias Panzenboeck wrote:
But the question is: *IS* this derived work? I mean, it's not copied code.
It's the same hashing-logic, which I learned by watching pythons code.
given that it's only a few lines of code, and there's hardly any other
way to write those lines if you want to implement the same algorithm,
I'd say it falls under "fair use". crediting the Python developers in
the source code should be good enough.

</F>

Nov 25 '06 #4
Fredrik Lundh wrote:
Mathias Panzenboeck wrote:
>But the question is: *IS* this derived work? I mean, it's not copied
code.
It's the same hashing-logic, which I learned by watching pythons code.

given that it's only a few lines of code, and there's hardly any other
way to write those lines if you want to implement the same algorithm,
I'd say it falls under "fair use". crediting the Python developers in
the source code should be good enough.

</F>
ic. I'll write a mail to the python developers then.

The code in python looks like this (see code underneath), just if someone what's to know.
I only used the logic of the parts I understand. ;)

Objects/stringobject.c:

static long
string_hash(PyStringObject *a)
{
register Py_ssize_t len;
register unsigned char *p;
register long x;

if (a->ob_shash != -1)
return a->ob_shash;
len = a->ob_size;
p = (unsigned char *) a->ob_sval;
x = *p << 7;
while (--len >= 0)
x = (1000003*x) ^ *p++;
x ^= a->ob_size;
if (x == -1)
x = -2;
a->ob_shash = x;
return x;
}

Objects/dictobject.c:

static dictentry *
lookdict_string(dictobject *mp, PyObject *key, register long hash)
{
register size_t i;
register size_t perturb;
register dictentry *freeslot;
register size_t mask = (size_t)mp->ma_mask;
dictentry *ep0 = mp->ma_table;
register dictentry *ep;

/* Make sure this function doesn't have to handle non-string keys,
including subclasses of str; e.g., one reason to subclass
strings is to override __eq__, and for speed we don't cater to
that here. */
if (!PyString_CheckExact(key)) {
#ifdef SHOW_CONVERSION_COUNTS
++converted;
#endif
mp->ma_lookup = lookdict;
return lookdict(mp, key, hash);
}
i = hash & mask;
ep = &ep0[i];
if (ep->me_key == NULL || ep->me_key == key)
return ep;
if (ep->me_key == dummy)
freeslot = ep;
else {
if (ep->me_hash == hash && _PyString_Eq(ep->me_key, key))
return ep;
freeslot = NULL;
}

/* In the loop, me_key == dummy is by far (factor of 100s) the
least likely outcome, so test for that last. */
for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
i = (i << 2) + i + perturb + 1;
ep = &ep0[i & mask];
if (ep->me_key == NULL)
return freeslot == NULL ? ep : freeslot;
if (ep->me_key == key
|| (ep->me_hash == hash
&& ep->me_key != dummy
&& _PyString_Eq(ep->me_key, key)))
return ep;
if (ep->me_key == dummy && freeslot == NULL)
freeslot = ep;
}
}
Nov 25 '06 #5
Fredrik Lundh wrote:
Mathias Panzenboeck wrote:
>But the question is: *IS* this derived work? I mean, it's not copied code.
It's the same hashing-logic, which I learned by watching pythons code.

given that it's only a few lines of code, and there's hardly any other
way to write those lines if you want to implement the same algorithm,
I'd say it falls under "fair use". crediting the Python developers in
the source code should be good enough.
If you'll forgive my pedantry, that's not "fair use," but simply the use of
material that cannot be copyrighted by itself (in many jursidictions, at least)
because it is so short, obvious, non-creative, etc.

A good overview of fair use is here:

http://fairuse.stanford.edu/Copyrigh...er9/index.html

IANAL. TINLA.

--
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
that is made terrible by our own mad attempt to interpret it as though it had
an underlying truth."
-- Umberto Eco

Nov 25 '06 #6

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
by: Christian Hackl | last post by:
I honestly wasn't able to find an answer for this design question using Google and Google Groups, so I apologize if it is asked too frequently :) Anyway: Let's say I have a multidimensional array...
9
by: ForHimself Every Man | last post by:
What's better about Rattlesnakes than Python. I'm sure there's something. What is it? This is not a troll. I'm a snake shooping and I want people's answers. I don't know beans about...
5
by: R. Rajesh Jeba Anbiah | last post by:
I could see that it is possible to have hash array using objects like var hash = {"a" : "1", "b" : "2"}; Couldn't still findout how to declare hash array in Array. var arr = new Array("a" : "1",...
21
by: CBFalconer | last post by:
I released this under GPL some time ago, (2003-May) and have been advertising it occasionally here, where it seemed applicable. I have received no bug reports. I have just gotten around to...
2
by: rtilley | last post by:
Is there a road map for python a 2.5 releases yet? I'd like to begin testing the new hashlib module with some old scripts I have that currently use the md5 and sha modules. Thanks, Brad
17
by: John A Grandy | last post by:
For a Hashtable that is expected to contain no more than 100 DictionaryEntry elements , what is the best load factor ? ( This Hashtable is a encapsulted in a class , an instance of which is...
3
by: Jonay Aloat | last post by:
I need to implement the following. Shoul I use multimap or write a string hash class? ie Brand Product ========================== Samson ...
0
by: CBFalconer | last post by:
I have revised my hashlib package, it can now handle something like 48,000,000 entries. At this level (about 8,000,000 up) you may run into problems with your systems malloc/free package. However...
9
by: smartbei | last post by:
Hello, I am a newbie with python, though I am having a lot of fun using it. Here is one of the excersizes I am trying to complete: the program is supposed to find the coin combination so that with...
2
by: Kemmylinns12 | last post by:
Blockchain technology has emerged as a transformative force in the business world, offering unprecedented opportunities for innovation and efficiency. While initially associated with cryptocurrencies...
0
by: antdb | last post by:
Ⅰ. Advantage of AntDB: hyper-convergence + streaming processing engine In the overall architecture, a new "hyper-convergence" concept was proposed, which integrated multiple engines and...
0
hi
by: WisdomUfot | last post by:
It's an interesting question you've got about how Gmail hides the HTTP referrer when a link in an email is clicked. While I don't have the specific technical details, Gmail likely implements measures...
0
Oralloy
by: Oralloy | last post by:
Hello Folks, I am trying to hook up a CPU which I designed using SystemC to I/O pins on an FPGA. My problem (spelled failure) is with the synthesis of my design into a bitstream, not the C++...
0
by: Carina712 | last post by:
Setting background colors for Excel documents can help to improve the visual appeal of the document and make it easier to read and understand. Background colors can be used to highlight important...
2
by: Ricardo de Mila | last post by:
Dear people, good afternoon... I have a form in msAccess with lots of controls and a specific routine must be triggered if the mouse_down event happens in any control. Than I need to discover what...
1
by: Johno34 | last post by:
I have this click event on my form. It speaks to a Datasheet Subform Private Sub Command260_Click() Dim r As DAO.Recordset Set r = Form_frmABCD.Form.RecordsetClone r.MoveFirst Do If...
1
by: ezappsrUS | last post by:
Hi, I wonder if someone knows where I am going wrong below. I have a continuous form and two labels where only one would be visible depending on the checkbox being checked or not. Below is the...
0
DizelArs
by: DizelArs | last post by:
Hi all) Faced with a problem, element.click() event doesn't work in Safari browser. Tried various tricks like emulating touch event through a function: let clickEvent = new Event('click', {...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.