Avatar billede myplacedk Nybegynder
20. juli 2003 - 21:59 Der er 18 kommentarer og
1 løsning

Feedback på stil til C-newbie

Som nævnt i en anden kategori, har jeg brug for at beregne en id ud fra en mp3-fil. Kravet er at id'en er den samme, selv om filen bliver flyttet, omdøbt eller får fjernet/tilføjet/ændret id3-tags.

Jeg har nu fundet en algoritme, som ser ud til at fungere. Jeg har forsøgt at implementere den i C++, og det ser også ud til at fungere. Men da jeg er en C(++)-newbie vil jeg gerne have feedback på min kode.

- Er der noget som inviterer til problemer?
- Er der noget som gøres bedre/nemmere/mere effektivt på en anden måde?
- Er der noget som ser ud til at være direkte fejl?

Det er en del af et program til håndtering af musik-samlinger. Jeg har planer om at udgive programmet under GPL.

Algoritmen:
Først tjekkes om det overhovedet er en mp3-fil. Dette gøres ved at se om de tre første bytes er "ID3", eller de 12 første bits er sat. Er en af delene opfyldt, formodes det at være en mp3-fil.

ID3-tags er 128 bytes tilføjet i slutningen af mp3-filen. De 128 bytes starter med strengen "TAG". Dvs. starter de sidste 128 bytes med "TAG", så skal disse 128 bytes ignoreres.

Der beregnes så en id ud fra den del af filen, der ikke er id3-tags. Id'en er "md5-agtig". Dvs. den består af 16 bytes, og vises som en streng med 32 tegn, som er tal fra 0-9 og bogstaverne A-F.
De 16 bytes fyldes først med de 16 første bytes fra filen, fra venstre (index 0) mod højre (index 15). Hele filen (undtagen id3) køres så igennem, hvor der hele tiden fyldes  på fra venstre mod højre. Ligesom når man skriver igen og igen på samme linje, på et stykke papir.
Data kombineres med eksisterende data via XOR.

Hvis man ændrer så meget som én vilkårlig bit i filen (stadig id3 undtaget), vil id'en ændre sig. Sandsynligheden for at id'en for to forskellige filer er ens, er forhåbentlig noget i stil med md5.

Jeg har valgt ikke at bruge md5 af flere årsager. Det kan koges ned til at dette er lettere for mig (tilsyneladende uden at miste noget væsentligt), og så bruger det vist også væsentligt mindre CPU-kraft. (Ret væsentligt når man lige skal køre 3 gb mp3'er igennem.)
Eneste ulempe jeg lige kan komme på er, at det er nemt at skabe en bestemt id.
Men det er da muligt at jeg på et tidspunkt vælger at bruge md5 i stedet for dette simple XOR.


Koden:
/*
* boolean file2id(char id[], char file[])
*
* Generates an id for an mp3. The id should not change if file is moved,
* renamed, or have id3-tags added, removed or changed.
*
* Parameters:
* char id[]: The id will be saved in this var, as a 32 bytes string (plus a
* null byte). The string only have digits and letters from A to F.
* char file[]: Path and filename to an mp3 file.
*
* Returns.
* Boolean: True on success, false if id could not be generated. Reasons for
* failure includes file not readable and file not recognized as MP3.
*
* Note: printf messages is only for debug purposes, will be removed later.
* (FIXME)
*/

bool file2id(char id[], char file[]) {
  FILE *fp; 
  unsigned char buf[3];
  long bytestoread;
  unsigned char sum[17];
  char dec2hex[] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};

  printf("Making ID from: %s\n", file);
  fp = fopen(file, "rb");
  if (!fp) {
    printf("  Couldn't open file for reading\n");
    return false;
  }
 
  fread(buf, 3, 1, fp);
  if (buf[0]!='I' || buf[1]!='D' || buf[2]!='3') {
    // File does not start with "ID3".
    buf[0] &= 0xff;
    buf[1] &= 0xf0;                                                       
    if(buf[0]!=0xff  || buf[1]!=0xf0){
      // The first 12 bits isn't all set, it's not an mp3-file.
      printf("  Is not an MP3-file\n");
      fclose(fp);
      return false;
    }
  }

  if (fseek(fp, -128, SEEK_END) != 0) {
    printf("  Could not seek to 128 bytes before end.\n");
    fclose(fp);
    return false;
  }

  fread(buf, 1, 3, fp);
  if (buf[0]!='T' || buf[1]!='A' || buf[2]!='G') {
    // The last 128 bytes does not start with "TAG", no ID3-tags.
    printf("  File does NOT have ID3 tags, making checksum of entire file.\n");
    fseek(fp, 0, SEEK_END);
  } else {
    printf("  File DOES have ID3 tags, don't use last 128 bytes in checksum.\n");
    fseek(fp, -128, SEEK_END);
  }

  bytestoread = ftell(fp); /* If there's id3-tags, this will be the filesize
                  minus the id3-tags. This way, added, removed or
                  changed ID3-tags will not be seen. */

  fseek(fp, 0, SEEK_SET); // Go to start of file.

  for (int i=0; i<bytestoread; i++) {
    sum[i%16] ^= fgetc(fp); /* FIXME: Errorhandling. If something changes, or
                  parts of file is unreadable, wrong id might be
                  generated with no way of knowing that something
                  is wrong. */
  }

  // sum should now be 16 bytes, 16 numbers between 0 and 255.

  // Let's convert those 16 bytes to a 32 chars, "md5-style".

  for (int i=0; i<16; i++) {
    id[i*2] = dec2hex[sum[i]/16];
    id[i*2+1] = dec2hex[sum[i]%16];
  }

  id[32] = '\0'; // Makes it a string with a null in the end.

  return true;
}
Avatar billede arne_v Ekspert
20. juli 2003 - 22:10 #1
Kommentarer:

1)  Du har selvfølgelig overvejet at uanset hvilken algoritme du bruger
    så er der en lille mulighed for at to forskellige giver samme værdi.

2)  I.s.f. din simple XOR af 16 byte blokke ville jeg nok overveje at
    bruge noget CRC. CRC er beregnet til at løse denne opgave. CRC er dog
    normalt kun 4 byte ikke 16 byte men der kunne man jo nok lave noget
    smart.

3)  Du bør erstatte fgetc med nogle fread som læser mega store klmuper.
    Det vil forbedre performance meget.
Avatar billede myplacedk Nybegynder
20. juli 2003 - 22:32 #2
1) Yeps. Det kan vist kun undgås ved at bruge hele filen som id, og det er ikke praktisk. ;-)
Med 16 bytes skulle risikoen være til at leve med.

2) Jeg har ikke studeret CRC, men så vidt jeg ved er det beregnet til at se, om en fil har ændret sig (fx. fejl ved overførelse eller på lagermedie). Her skal det bruges til at genkende en fil blandt tusindvis af andre.
Hvad er fordelen ved CRC?
4 bytes er måske nok, men jeg synes ikke det "føles" rigtigt. Og jeg kan ikke lige se fordelen...

3) Tanken med fgetc er, at jeg alligevel kun bruger én byte af gangen. Men hvis den ikke er buffered (kan jeg så gætte mig til at den ikke er), så har nu nok ret i at det ville være godt at lave en buffer.
Fx. noget med at hente 1 mb(?) af gangen, og så køre for-løkken på hver "bid"?
Det er nok lige præcis de få linjer, som bliver det alt-afgørende i performance. Nogle har jo en samling på mange gb, som skal læses byte for byte...
Tror du 1 mb er en passende klump at tage af gangen? Hvis du vil skrive de par linjer om, vil jeg blive *meget* glad. :)
I resten af programmet er performance ikke så vigtigt, i hvert fald ikke foreløbigt. Men lige denne stump er som sagt vigtig...
Avatar billede arne_v Ekspert
20. juli 2003 - 22:37 #3
Jeg er overbevist om at fread med en stor buffer vil være betydeligt
hurtigere end fgetc. Men præcis hvor emeget vil afhænge meget
af platform og compiler.

Min *fornemmelse* siger mig at gevindsten ved buffer > 100 KB vil være
beskeden.

Men prøv og lav dine egne eksperimenter.
Avatar billede arne_v Ekspert
20. juli 2003 - 22:42 #4
"beregn en værdi for en stor klump bytes for at kunne teste om indholdet
har ændret sig"

"beregn en værdi for en stor klump bytes for at kunne se om indhold er
ens"

er præcis samme problem-stilling.

CRC er lavet specielt for at være god til at detecte forskelle.

Det er sikkert ikke nødvendigt til din problem-stilling. Men jeg ville
lige bringe det på bane.

At bruge CRC til 16 byte værdi er jo nemt. Bare lav 4 CRC'er. En for
byte 1-4, 17-20, 33-36 ... - en for 5-8, 21-24, ... - etc.etc..
Avatar billede myplacedk Nybegynder
20. juli 2003 - 23:17 #5
> ... er præcis samme problem-stilling.

Ja, men det var heller ikke det, jeg mente. :)

"Beregn en værdi for en fil, til at kontrollerer om to filer der burde være ens, også er det". (fejl-kontrol)

"Beregn en værdi for en fil, som er unik blandt tusindvis af filer."

Man kunne fx. nøjes med at bruge én bit. Den vil fange fejl med 50% sandsynlighed. Brugbart (hvem sagde paritetsram?), men flere bits er meget mere værd.
Men til at beregne et unikt id, vil du med 50% sandsynlighed få problemer allerede med to elementer. Med tre elementer kan det helt sikkert ikke fungere.

Men det var nu ikke det, det drejede sig om. ;-)

Jeg siger tak for feedback, jeg vil skrive om til at bruge fread i stedet for fgetc.

Jeg lader spørgsmålet stå åbent lidt endnu...
Avatar billede bertelbrander Novice
20. juli 2003 - 23:49 #6
C-standarden garanterer ikke at man kan søge fra enden af en fil med fseek(), hvis filen er binær.
Avatar billede arne_v Ekspert
21. juli 2003 - 07:44 #7
Jeg troede at det var den anden vej. At man altid kan bruge fseek
med en binær fil, men kun fseek til ftell værdi med tekst filer.
Avatar billede segmose Nybegynder
21. juli 2003 - 10:03 #8
Som jeg læser K&R2 har arne_v ret, grunden er formodentlig at at i tekst filer skal CR/LF omsættes og derfor bliver 2 karakter til 1 når de læses i visse operativ systemer.
Avatar billede dilleberg Nybegynder
21. juli 2003 - 12:01 #9
bertelbrander har ret.

C standarden siger om fseek():
"A binary stream need not meaningfully support fseek with a whence value of SEEK_END."

Det er altså positionering i forhold til enden af filen, der ikke garanteres.
Men jeg har aldrig oplevet problemet, hverken i Windows eller UNIX.

db
Avatar billede myplacedk Nybegynder
21. juli 2003 - 14:14 #10
> Men jeg har aldrig oplevet problemet, hverken i Windows eller UNIX.

Så er det nok ikke så vigtigt. Men alligevel: Er der så en måde til at finde filstørrelsen, som er mere pålidelig? I så fald kunne man jo blot køre fra starten, i stedet for slutningen. Men jeg har på fornemmelsen, at det netop er det med filstørrelsen, der er årsag til problemet...
Avatar billede segmose Nybegynder
21. juli 2003 - 14:25 #11
> dilleberg
Står der mere om hvorfor?
Avatar billede arne_v Ekspert
21. juli 2003 - 14:38 #12
myplace>

fstat/stat måske.
Avatar billede arne_v Ekspert
21. juli 2003 - 14:41 #13
Med hensyn til SEEK_END så må det vel være for at supportere fil systemer, hvor
man ikke har en faktisk størrelse gemt.

(selvom det er lidt svært at forestille sig et sådant)
Avatar billede dilleberg Nybegynder
21. juli 2003 - 15:41 #14
Jeg har oplevet i hvert fald et filsystem, hvor filstørrelsen blev angivet i segmenter på 768 bytes (= 3/4 KByte !!) Filen blev så fyldt med efterstillede nuller, så størrelsen altid var et multiplum af 768. I et sådan system kan man ikke umiddelbart positionere i forhold til sidste byte.
Det må være forklaringen på SEEK_END begrænsningen.

myplace> Jeg kan ikke forestille mig, at det ikke vil fungere på et moderne filsystem.

Med hensyn til id3 tags er der en interessant side her:
http://www.id3.org/

Et glimrende eksempel på CRC32:
http://www.codeproject.com/cpp/crc32.asp?target=crc32

db
Avatar billede bertelbrander Novice
21. juli 2003 - 19:59 #15
Udover dillebergs citat er der følgende note i C-standarden:
<citat>
209) Setting the file position indicator to end-of-file, as with fseek(file, 0, SEEK_END), has undefined behavior for a binary stream (because of possible trailing null characters) or for any stream with state-dependent encoding that does not assuredly end in the initial shift state.
</citat>
Jeg ved ikke hvad en "shift state" er...
Avatar billede arne_v Ekspert
21. juli 2003 - 20:09 #16
Men næppe noget problem.

Og hvis fseek fra SEEK_END ikke virker så tror jeg heller ikke
at fseek til noget fra fstat/stat virker.
Avatar billede myplacedk Nybegynder
21. juli 2003 - 21:10 #17
arne_v > Det er også min foreløbige konklusion. :)

Jeg takker for hjælpen. Hvis der er andre end arne_v, der vil have lidt point, så smid lige et svar. :)
Avatar billede arne_v Ekspert
31. juli 2003 - 08:15 #18
Tid at lukke spørgsmålet ?
Avatar billede myplacedk Nybegynder
31. juli 2003 - 16:57 #19
Yep, sorry, troede egentlig jeg havde gjort det. :)
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Kurser inden for grundlæggende programmering

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester