taskSavannah Administration - Tasks: task #10138, Submission of Swiss army knife of...

 
 

task #10138: Submission of Swiss army knife of file signature checksum tool

Submitter:  Tong Sun <xpt>
Submitted:  Mon 01 Feb 2010 05:56:16 PM UTC
   
 
Should Start On:  Mon 01 Feb 2010 05:00:00 AM UTC Should be Finished on:  Thu 11 Feb 2010 05:00:00 AM UTC
Category:  Project Approval Priority:  * 5 - Normal
Status:  Done Privacy:  Public
Assigned to:  marioxcc Open/Closed:  Closed
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Wed 10 Feb 2010 02:56:16 PM UTC, comment #7: 


> >Hope that I've clarified everything. Would my project be now cleared
> >for approval?
>
> Yes, it is, enjoy mantaining it at savannah, the url is
> http://savannah.gnu.org/p/checksum
>
> Item status changes:
>
> Status -> Done
> Open/Closed -> Closed


Thanks a lot, I'll start working.

Tong Sun <xpt>
Wed 10 Feb 2010 02:07:21 AM UTC, comment #6: 

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

February 9th 2010 in GNU Savannah task 10138: "Submission of Swiss
army knife of file signature checksum tool"

>Yes, I need to implement the IEEE 802.3 that most CRC32 commands use,
>eg. .sfv files.


I don't know the polynomials of the different existing impementations,
so I can't further help on this.

Please note that md4 is specified as an secure algorithm, but there
are atacks and know colisions againsting it, so is not longer secure
in the cyptography sense.  However, it is still an fast (Because it
simplicity) and secure (Because it length, 128 bits) algorithm for
chech for random errors only.

>Hope that I've clarified everything. Would my project be now cleared
>for approval?


Yes, it is, enjoy mantaining it at savannah, the url is
http://savannah.gnu.org/p/checksum

Item status changes:

Status -> Done
Open/Closed -> Closed
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEAREIAAYFAktyFLsACgkQZ4DA0TLic4g5lACbBb7ups63wEbZANVPFWgg6w0o
GsAAn1O2lzLq9r82TFR3Rm2U930aYai5
=MMYy
-----END PGP SIGNATURE-----

Mario Castelán Castro <marioxcc>
Mon 08 Feb 2010 03:14:27 PM UTC, comment #5: 


> Additional Item Attachment, task #10138 (project administration):
> File name: dev_jackmaster-0.0.2.tar.bz2   Size:40 KB


hmmm....

jackmaster - A "Master Console" for the jack-audio-connection-kit

I think it is added by mistake.

Tong Sun <xpt>
Mon 08 Feb 2010 01:08:01 AM UTC, comment #4: 


> You must label, at least inside savannah your projects as free


Oh, thought it'd be obvious. Sure will do.

> Do you need to use an particular polynomial for the CRC?


Yes, I need to implement the IEEE 802.3 that most CRC32 commands use, eg. .sfv files.

> I'm not sure, but I think MD4 is faster than CRC32 in software


Thanks for the advice, I'll add MD4 as well. I've found the OpenBSD's implementation:

  /*      $OpenBSD: md4.c,v 1.7 2005/08/08 08:05:35 espie Exp $   */

  /*
   * This code implements the MD4 message-digest algorithm.
   * The algorithm is due to Ron Rivest.  This code was
   * written by Colin Plumb in 1993, no copyright is claimed.
   * This code is in the public domain; do with it what you wish.
   * Todd C. Miller modified the MD5 code to do MD4 based on RFC 1186.
   *
   * Equivalent code is available from RSA Data Security, Inc.
   * This code has been tested against that, and is equivalent,
   * except that you don't need to include two pages of legalese
   * with every copy.
   *
   * To compute the message digest of a chunk of bytes, declare an
   * MD4Context structure, pass it to MD4Init, call MD4Update as
   * needed on buffers full of bytes, and then call MD4Final, which
   * will fill a supplied 16-byte array with the digest.
   */

Hope that I've clarified everything. Would my project be now
cleared for approval?

thanks

Tong Sun <xpt>
Sun 07 Feb 2010 10:43:05 PM UTC, comment #3: 

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

February 7th 2010 in GNU Savannah task 10138: "Submission of Swiss
army knife of file signature checksum tool"

Thanks for your fast response Tong.

>As for crc32.c, the zlib crc32 function can't be used directly since
>it is using the 0xFFFFFFFF pre & post condition [...]


Do you need to use an particular polynomial for the CRC?

The program will not interfact to libogg or any other, true?, then you
can use any polynomial for the CRC, or use another algorithm instead.

I'm not sure, but I think MD4 is faster than CRC32 in software since
it is not complex and it works by wide blocks, not by stream like CRC.
Apart it result is wider, so random colisions are more unlikley than
with CRC.

The above is just technical advice, you are not required to use any
particular algorithm to host in savannah.  Patented ones can't be used
in free software, since they impose propietary, unacceptable
restictions, there are a few exeptions like CAST4, wich is patented
but can be freely used.

>However, there is no copyright and licensing info in source. I've
>written to the author since, but haven't get reply yet:


Note that in GNU project (And therefore in Savannah, part of the GNU
project) we don't support the open source software but the free (As in
freedom) one, plese read
http://www.gnu.org/philosophy/open-source-misses-the-point.html.

You must label, at least inside savannah your projects as free, that
is a requirement: https://savannah.gnu.org/register/requirements.php.

Remember, Copyright don't cover ideas by itself but the manner they
are expressed.  You can rewrite any software (Unless it is cover by
patents) keeping the same algorithm and design, If the result don't
seems related to the "original" version then you can assign the
copyright of the revised version to you, and release it under a free
licence of your choice (I suggest the GNU GPL of course, but that is
up to you).

So if the author of the CRC implementation you want to use don't
release it as free software, or you don't want to wait, rewrite it
from scratch, or use another hash instead (Like sugessted above).

Regards.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEAREIAAYFAktvQfQACgkQZ4DA0TLic4hCwgCfT2zqfLJ9HsRomF4p2uY0SHSM
HJcAn1p08Tug6WAu22OrLTvufUpsnmE/
=gu4P
-----END PGP SIGNATURE-----

Mario Castelán Castro <marioxcc>
Sun 07 Feb 2010 09:10:04 PM UTC, comment #2: 

Thanks to your reply, Mario.

I'll use the win/md5.c file, the public domain one, as per your suggestion.

> In GNU Savannah we host only GPL-compatible (With

any present or future version) material

I saw "Modified BSD License" is still an option. Would it be OK to release my project as "Modified BSD License"? Reason follows.

As for crc32.c, the zlib crc32 function can't be used directly since it is using the 0xFFFFFFFF pre & post condition --
http://lists.xiph.org/pipermail/ogg-dev/2008-February/000803.html
However, I've found a good alternative, even faster than zlib's -- Slicing-by-8 CRC32 Implementation
http://www.slapmahfro.net/news.php?2009-11

However, there is no copyright and licensing info in source. I've written to the author since, but haven't get reply yet:

From: Tong Sun <...@cpan.org>
Date: Mon, Feb 1, 2010 at 7:15 PM
Subject: Your Slicing-by-8 CRC32 Implementation
To: -email is unavailable-

Hi Brian,

I'd like to borrow your Slicing-by-8 CRC32 Implementation and use it in my open source project, which is pending to be hosted on http://www.nongnu.org/. (my current one there is http://www.nongnu.org/qdiff/).

I need your written permission in doing so, and your copyright and licensing info as well.

Moreover, I don't know how much your code depends on Intel's Implementation. I mean, I took a look at their copyright and licensing:

  • Copyright (c) 2004-2006 Intel Corporation - All Rights Reserved

 *


and hope you release your code in BSD License as well.

Thanks

Tong Sun <xpt>
Sun 07 Feb 2010 08:38:25 PM UTC, comment #1: 

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

February 7th 2010 in GNU Savannah task 10138: "Submission of Swiss
army knife of file signature checksum tool"

Hi,

Sorry for slow response, I'm evaluating the project you submitted for
approval in Savannah.

Please state the copyright holder of crc32.c and clarify if there is
the right to modify the file, if you don't know this information
replace for a crc32.c from zlib or any other for wich the copyright
holder and exact copyright terms are known.

The fils unix/md5.* are not GPL-compatible because they requires you
to mark derived works as "derived from the RSA Data Security, Inc. MD5
Message-Digest Algorithm" in all material mentioning or referencing
the derived work.  In GNU Savannah we host only GPL-compatible (With
any present or future version) material, so please replace that file
with a GPL-compatible version like the one in win/md5.c, wich is
public domain.

Also, please if possible put the files inside a directory in the
tarball. Is not mandatory but is a de facto standard and makes life
easy to users. If files are in root of tarball one must create an
directory, move the tarball and uncompress it instead of only unpack
the tarball directly.

Item status changes:

Assigned to -> marioxcc
Status -> In progress
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEAREIAAYFAktvJL0ACgkQZ4DA0TLic4jr5gCfelgb0br9xlCZ4Kcq+6EbMQ4B
WUsAn2/V22LiJb9WJvv4wGA3Um8i0afZ
=ibi1
-----END PGP SIGNATURE-----

Mario Castelán Castro <marioxcc>
Mon 01 Feb 2010 05:56:16 PM UTC, original submission:  

A new project has been registered at Savannah
This project account will remain inactive until a site admin approves or discards the registration.


Registration Administration


While this item will be useful to track the registration process, approving or discarding the registration must be done using the specific Group Administration page, accessible only to site administrators, effectively logged as site administrators (superuser):



Registration Details


  • Name: Swiss army knife of file signature checksum tool
  • System Name:  checksum
  • Type: non-GNU software & documentation
  • License: Modified BSD License





Description:

checksum is a versatile checksum creator and verifier. It support crc32 and md5 algorithms. It can compute/verify signatures from files (with names given from either commandline or stdin pipe), from given directory or text argument from commandline. It understand/verify common file formats like .sfv or .md5.

Most importantly, it can remove duplicated files, i.e., identify distinct files with identical content within the given directory using the file signatures, and link them together to save disk space.

programming language: C

What is special about it?

There is only one tools written in C to check and remove duplicated files -- the dupmerge, but I found its algorithm inefficient and slow:

,-----
| Dupmerge works by quicksorting a list of path names, with the
| actual unlinking and relinking steps performed as side effects of
| the comparison function. The results of the sort are discarded.
`-----

The algorithm is inefficient and slow because:

- File contents are compared each time in the O(n*ln(n)) comparison.
- It doesn't provide an option to only check same-name files to speed up the process.
Ref: https://sourceforge.net/projects/dupmerge/forums/forum/427960/topic/3536512
- My approach will not only omit file-contents comparison each time, but also bring down the complexity from O(n*ln(n)) to near linear comparison, thanks to the introduced file signature.
- The other advantage over dupmerge is that, using quicksort, the file list has to be store in memory, which imposes a barrier to deal with a big number of files with small memory. My checksum does not has such problem at all.




Other Software Required:

MD5 message-digest algorithm, RSA Data Security, Inc.
=====================================================

 Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All
rights reserved.

License to copy and use this software is granted provided that it
is identified as the "RSA Data Security, Inc. MD5 Message-Digest
Algorithm" in all material mentioning or referencing this software
or this function.

License is also granted to make and use derivative works provided
that such works are identified as "derived from the RSA Data
Security, Inc. MD5 Message-Digest Algorithm" in all material
mentioning or referencing the derived work.

RSA Data Security, Inc. makes no representations concerning either
the merchantability of this software or the suitability of this
software for any particular purpose. It is provided "as is"
without express or implied warranty of any kind.

These notices must be retained in any copies of any part of this
documentation and/or software.


32-bit CRC, ANSI X3.66
======================

The computing of the 32-bit CRC is used as the frame check sequence in ADCCP
(ANSI X3.66, also known as FIPS PUB 71 and FED-STD-1003, the U.S. versions
of CCITT's X.25 link-level protocol).  The 32-bit FCS was added via the
Federal Register, 1 June 1982, p.23798.




Other Comments:

Half way done. No tarball to upload. Need the git to keep dev versions. The uploaded tarball is just to satisfy the project registration.



Tarball URL:

http://savannah.gnu.org/submissions_uploads/checksum.tgz


Tong Sun <xpt>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #19646:  dev_jackmaster-0.0.2.tar.bz2 added by None (41KiB - application/x-tar)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by marioxcc (Posted a comment)
  • -email is unavailable- added by xpt (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.

     

    Follow 5 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2010-02-10 marioxcc StatusIn Progress Done
        Open/ClosedOpen Closed
    2010-02-08 None Attached File- Added dev_jackmaster-0.0.2.tar.bz2, #19646
    2010-02-07 marioxcc StatusNone In Progress
        Assigned toNone marioxcc

    Back to the top

    Powered by Savane 3.13-02a9.
    Corresponding source code