Page 1 of 1

An example of code copying (IvanHoe) ?

Posted: Thu Jan 27, 2011 3:19 am
by BB+
So in the RobboBase compression code of IvanHoe, there's a comment at one point:
Suffix_fare (bufI, indici, pro); /* larsson plus sadakane */
The Larsson-Sadakane algorithm for computing suffix trees seems to be indicated. This is included in the "Robbo_suffix.c" file. Looking at Larsson's homepage, I find http://www.larsson.dogma.net/qsufsort.c as the code coming out of their paper.

Now compare those two files. It seems like the RobboBase version has managed to rewrite much of it to avoid a lot of the pointer arithmetic, and they have no need of the "transform" operation with an initial bucketsort (presumably the data is already sufficiently pre-processed), but other than that, there appears to be a large commonality of code. Whether or not it is "copying" is a different matter.

Here is an example (from the main functions of each):

Code: Select all

   while (*I>=-n) {
      pi=I;                     /* pi is first position of group.*/
      sl=0;                     /* sl is negated length of sorted groups.*/
      do {
         if ((s=*pi)<0) {
            pi-=s;              /* skip over sorted group.*/
            sl+=s;              /* add negated length to sl.*/
         } else {
            if (sl) {
               *(pi+sl)=sl;     /* combine sorted groups before pi.*/
               sl=0;
            }
            pk=I+V[s]+1;        /* pk-1 is last position of unsorted group.*/
            sort_split(pi, pk-pi);
            pi=pk;              /* next group.*/
         }
      } while (pi<=I+n);
      if (sl)                   /* if the array ends with a sorted group.*/
         *(pi+sl)=sl;           /* combine sorted groups at end of I.*/
      h=2*h;                    /* double sorted-depth.*/
   }

Code: Select all

  while (IDX[0] > -N)
    {
      w = 0;
      sort_run = 0;
      while (w < N)
        {
          ind = IDX[w];
          if (ind < 0)
            {
              w += -ind;
              sort_run += -ind;
            }
          else
            {
              if (sort_run)
                {
                  IDX[w - sort_run] = -sort_run; /* negate for packet */
                  sort_run = 0;
                }
              MainSorter (IDX, AUX, N, h, w, AUX[ind]);
              w = AUX[ind] + 1;
            }
        }
      if (sort_run)
        IDX[w - sort_run] = -sort_run;
      h <<= 1; /* double */
   }
Similarly, compare MainSorter to sort_split, PivotSelectionValue to choose_pivot, SelectionSorter to select_sort_split, and SamePacket to update_group.

Re: An example of code copying (IvanHoe) ?

Posted: Thu Jan 27, 2011 3:53 am
by kingliveson
I haven't looked at it yet, but they can easily correct it:

Code: Select all

/* qsufsort.c
   Copyright 1999, N. Jesper Larsson, all rights reserved.

   This file contains an implementation of the algorithm presented in "Faster
   Suffix Sorting" by N. Jesper Larsson (jesper@cs.lth.se) and Kunihiko
   Sadakane (sada@is.s.u-tokyo.ac.jp).

   This software may be used freely for any purpose. However, when distributed,
   the original source must be clearly stated, and, when the source code is
   distributed, the copyright notice must be retained and any alterations in
   the code must be clearly marked. No warranty is given regarding the quality
   of this software.*/

Re: An example of code copying (IvanHoe) ?

Posted: Thu Jan 27, 2011 4:01 am
by BB+
I haven't looked at it yet, but they can easily correct it:
Yes, I saw the copyright notice too, but my point was how one can "morph" code and leave others to wonder whether it is a "copy", or a "rewrite", or a maybe they just read the paper and took the code as a "spec" --- hmm, perhaps it's as you said before, that the IvanHoe crew is always trying to tell us something in their own peculiar way...

Re: An example of code copying (IvanHoe) ?

Posted: Thu Jan 27, 2011 4:06 am
by kingliveson
BB+ wrote:
I haven't looked at it yet, but they can easily correct it:
Yes, I saw the copyright notice too, but my point was how one can "morph" code and leave others to wonder whether it is a "copy", or a "rewrite", or a maybe they just read the paper and took the code as a "spec" --- hmm, perhaps it's as you said before, that the IvanHoe crew is always trying to tell us something in their own peculiar way...
Reading the license again, and re-reading your comment, I see what you mean...but who knows :?

Re: An example of code copying (IvanHoe) ?

Posted: Thu Jan 27, 2011 4:11 am
by BB+
Reading the license again, and re-reading your comment, I see what you mean...but who knows :?
For that matter, did you catch what they put at the top of the GPL (in the COPYING file) in ComStock?

Re: An example of code copying (IvanHoe) ?

Posted: Thu Jan 27, 2011 4:31 am
by kingliveson
BB+ wrote:
Reading the license again, and re-reading your comment, I see what you mean...but who knows :?
For that matter, did you catch what they put at the top of the GPL (in the COPYING file) in ComStock?
Not until you mentioned it... ;)