20. juli 2003 - 21:59Der 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) */
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".
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.
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...
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.
"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.
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.
> 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...
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.
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...
Yep, sorry, troede egentlig jeg havde gjort det. :)
Synes godt om
Ny brugerNybegynder
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.