[C++/Hex] Offsets lezen en schrijven van hex-pairs

[Arcane Apex]

Voor een CS project dien ik te weten hoe men de offset van een hexadecimale pair kan uitlezen en tevens hoe men een bepaalde hexadecimale pair een specifieke offset kan geven.

Om het even wat duidelijker uit te leggen. Stel je opent een .txt bestand in een hex-editor, dan zie je de bit-stream van het .txt bestand hexadecimaal weergegeven. Wat je tevens in de hex-editor zult zien zijn de offsets van de hex pairs. Voorbeeld:

code:

Offset
00000000     68 61 6C 6C 6F       hallo

De bovenstaande bit stream welke getoond wordt door de 5 hexadecimale pairs zorgt ervoor dat het woord "hallo" in ASCII wordt getoond in het desbetreffende .txt bestand.

Elk van de hex-pairs heeft zijn eigen offset. Een offset is een relatief memory adres.
De pair "68" heeft als offset "00000000". De pair 61 heeft als offset "00000001" en de pair 6F heeft als offset "00000004".

Nu is mijn vraag alsvolgt. Hoe kan met behulp van C++ de offset van een specifieke hex-pair te weten komen en dus uitlezen? En tevens hoe kan men een specifieke offset toewijzen aan een specifieke hex-pair.

Wanneer ik dus de offset van "61" uitlees hoor ik dus "00000001" als resultaat te krijgen. Maar daarnaast wil ik de offset van "61" ook kunnen veranderen. Dan zou je zeggen, ok waarom verplaats je niet gewoon de letter "a" naar de plek in de bit stream die jij wilt? Nou stel dat ik dat zou doen, dan zou het woord "hallo" niet meer correct verschijnen in het .txt bestand, het woord zou dan namelijk veranderen en daarmee de betekenis en dat wil ik dus niet.

Ik wil dus aan een hex-pair een offset geven die ik wil, maar zonder de volgorde te veranderen! Dat betekent dat "61" dus best als offset "00000007" mag krijgen, want dat is hoger dan "00000000", dus de "a" zal dan altijd na de "h" komen. De letters die na de "a" komen zullen dan een offset moeten krijgen welke hoger is dan "00000007" om de volgorde van de letters in stand te houden. Ik wil de offsets van de hex-pair vervolgens schrijven naar de hard disk.


Mijn vraag is dus, hoe kan ik de offset van een hex-pair blijvend veranderen in C++? (Blijvend, dus opgeslagen op de hard disk.)

[ Voor 3% gewijzigd door Arcane Apex op 16-08-2010 14:27 ]

[RobIII]

Ik kan er geen touw aan vastknopen maar je beseft dat hex enkel een representatie is van een willekeurige zooi bits? Zie Getallen en talstelsels FAQ en dan specifiek Representatie en opslag.

De offset is gewoon de positie in de file. De a van hallo staat dus op positie 0 (begin van de file) +1 = 000001. De H staat op positie 0 en de tweede L staat op 0 + 4. Zo moeilijk is dat toch niet?

Als je de offset zoekt van een bestaande byte (want dat zijn je "hex pairs" gewoon) dan zoek je gewoon die byte in de file. De positie is de offset.

[ Voor 56% gewijzigd door RobIII op 16-08-2010 14:30 ]

[MLM]

offset is gewoon de locatie van je pair in memory.
maar als jij de offset van een pair wilt weten in jouw voorbeeld, wat moet je dan terug krijgen als ik om 6C vraag? 2? 3? die relatie is niet echt logisch opgezet

C:

char *buffer = "hallo";
//buffer[offset] = pair
buffer[1] = 'e'; //nu is je buffer "hello", immers je hebt index 1 overschreven

als je wilt zoeken naar een karakter kan je gewoon memchr() gebruiken

[Arcane Apex]

RobIII schreef op maandag 16 augustus 2010 @ 14:26:
Ik kan er geen touw aan vastknopen maar je beseft dat hex enkel een representatie is van een willekeurige zooi bits? Zie Getallen en talstelsels FAQ

Dat besef ik. De hex-pairs staan in werkelijkheid voor 8-bits en dus 1-byte. Wat ik wil is de offset van een bepaalde byte kunnen achterhalen en tevens veranderen. Veranderen op zo'n manier dat de nieuwe offset welke ik aan de byte heb gegeven door de hard disk opgeslagen wordt, maar de volgorde van de letters in het woord "hallo" moet gewaarborgd blijven.

Dit soort dingen zijn eenvoudig te doen mbv pointers in het RAM geheugen, maar ik wil dit juist doen op de harde schijf, zodat de offsets die ik aan de hex-pairs gegeven heb blijvend opgeslagen worden.

[ Voor 18% gewijzigd door Arcane Apex op 16-08-2010 14:32 ]

[EddoH]

De 'offset' kan je niet veranderen. Een offset is gewoon relatieve adres ten opzichte van het startadres van de file.
Je vraagt nu om een volgorde van bytes in een file te veranderen, maar de originele volgorde overanderd te laten

[RobIII]

Arcane Apex schreef op maandag 16 augustus 2010 @ 14:29:
[...]


Dat besef ik. De hex-pairs staan in werkelijkheid voor 8-bits en dus 1-byte. Wat ik wil is de offset van een bepaalde byte kunnen achterhalen en tevens veranderen. Veranderen op zo'n manier dat de nieuwe offset welke ik aan de byte heb gegeven door de hard disk opgeslagen wordt.

Dan schrijf je toch gewoon op positie X in het bestand je byte? Alleen:

EddoH schreef op maandag 16 augustus 2010 @ 14:32:
De 'offset' kan je niet evranderen. Een offset is gewoon relatieve adres ten opzichte van eht startadres van de file.
Je vraagt nu om een volgorde van bytes in een file te veranderen, maar de originele volgorde overanderd te laten

Precies. Het ontgaat mij ook even wat nou precies de bedoeling is

[ Voor 30% gewijzigd door RobIII op 16-08-2010 14:33 ]

[Arcane Apex]

RobIII schreef op maandag 16 augustus 2010 @ 14:32:
[...]

Dan schrijf je toch gewoon op positie X in het bestand je byte? Alleen:

Nee, want zoals ik al aangaf in mijn 1ste post zou dat de het woord "hallo" veranderen en dat is juist niet de bedoeling. De volgorde van de letters dient gewaarborgt te blijven.

[Verwijderd]

Arcane Apex schreef op maandag 16 augustus 2010 @ 14:34:
[...]


Nee, want zoals ik al aangaf in mijn 1ste post zou dat de het woord "hallo" veranderen en dat is juist niet de bedoeling. De volgorde van de letters dient gewaarborgt te blijven.

Hoe verwacht je dat te kunnen doen? Als je bits gaat shiften dan verandert de representatie. De offset is geen getal welke ergens staat opgeslagen.

[jelmervos]

Arcane Apex schreef op maandag 16 augustus 2010 @ 14:34:
[...]


Nee, want zoals ik al aangaf in mijn 1ste post zou dat de het woord "hallo" veranderen en dat is juist niet de bedoeling. De volgorde van de letters dient gewaarborgt te blijven.

Je wilt dus gewoon iets toevoegen ipv bewerken?

[RobIII]

Arcane Apex schreef op maandag 16 augustus 2010 @ 14:34:
[...]


Nee, want zoals ik al aangaf in mijn 1ste post zou dat de het woord "hallo" veranderen en dat is juist niet de bedoeling. De volgorde van de letters dient gewaarborgt te blijven.

Dan schrijf je toch "Hallo" op locatie X Je kunt een offset niet wijzigen; een offset is gewoon een plek t.o.v. (in dit geval) het begin van je file. Een offset in het algemeen is gewoon een plek t.o.v. een andere plek.

[EddoH]

Arcane Apex schreef op maandag 16 augustus 2010 @ 14:29:
[...]

Dit soort dingen zijn eenvoudig te doen mbv pointers in het RAM geheugen, maar ik wil dit juist doen op de harde schijf, zodat de offsets die ik aan de hex-pairs gegeven heb blijvend opgeslagen worden.

Misschien kun je hier dan een voorbeeld van geven zodat we begrijpen wat je bedoeld?
De combinatie pointers en offsets ontgaat me ook volledig.....

[Arcane Apex]

EddoH schreef op maandag 16 augustus 2010 @ 14:32:
De 'offset' kan je niet veranderen. Een offset is gewoon relatieve adres ten opzichte van het startadres van de file.
Je vraagt nu om een volgorde van bytes in een file te veranderen, maar de originele volgorde overanderd te laten

Nee dat vraag ik juist niet. In mijn eerste post geef ik juist aan hoe men een offset kan veranderen zonder de volgorde te veranderen. Een hogere offset zal altijd na een lagere offset komen. De offset adressen van de hex-pairs zullen dan niet alleen ge-incrementeerd worden met 1, maar met "n+1", waarbij n voor elk positief getal kan staan. Ik weet dat het een beetje ingewikkeld klinkt, maar ik hoop dat iemand het begrijpt.

[gvdh]

Als ik het goed begrijp wil je van "HALLO" "H___ALLO" maken, waar op de plaats van de _ allemaal nulwaardes staan?
Dan zul je iets moeten doen zoals:
- Lees buffer in
- Schrijf in een nieuwe buffer de bytes één voor één weg en schrijf nul vanaf de oorspronkelijke offset tot de offset voor de nieuwe offset. Daarna verder bytes wegschrijven.

[jelmervos]

Je kunt een offset niet veranderen, vergelijk het met regelnummers voor een stuk tekst.

[RobIII]

Arcane Apex schreef op maandag 16 augustus 2010 @ 14:38:
[...]


Nee dat vraag ik juist niet. In mijn eerste post geef ik juist aan hoe men een offset kan veranderen zonder de volgorde te veranderen.

Je. Kunt. Een. Offset. Niet. Veranderen.
Wat jij wil is op een bepaald punt in je file een tekst schrijven.

Arcane Apex schreef op maandag 16 augustus 2010 @ 14:38:
maar ik hoop dat iemand het begrijpt.

Niet bepaald; je praat echt (met alle respect) compleet onzin.

[Verwijderd]

Ik heb het idee (en volgens mij ben ik niet de enige) dat je geen idee hebt waar je het over hebt. De offset staat nergens he. Je telt gewoon het aantal bits vanaf het begin en dat is je offset, maar dit wordt nergens opgeslagen.

[MSalters]

Ik denk dat je er verstandig aan doet om het gewenste eindresultaat in hetzelfde formaat eronder te zetten. Misschien iets als "Gewenst:"

code:

Offset
00000000     2D 2D 3E 68 61 6C 6C 6F       -->hallo

[RobIII]

Verwijderd schreef op maandag 16 augustus 2010 @ 14:41:
Je telt gewoon het aantal bits vanaf het begin en dat is je offset, maar dit wordt nergens opgeslagen.

Het aantal bytes

[ Voor 30% gewijzigd door RobIII op 16-08-2010 14:44 ]

[Verwijderd]

RobIII schreef op maandag 16 augustus 2010 @ 14:42:
[...]

Het aantal bytes

Dat ligt eraan hoe je je offset wilt representeren

[Reptile209]

Volgens mij probeer je dit te doen:
- vind de positie (offset) van een bepaalde byte-reeks (offset1)
- bepaal de nieuwe offset: offset2 = offset1 + verschuiving
- schrijf de eerste <offset1> bytes van de oude file weg naar een nieuwe file
- voeg <verschuiving> nieuwe bytes aan de nieuwe file toe (opvulling, garbage, ...)
- schrijf de rest (<offset1> tot en met EOF) van de oude file weg naar de nieuwe file.

Je bytereeks heeft in de nieuwe file nu de gewenste nieuwe offset, en alles voor en achter de bytereeks is onaangetast gebleven.

* Reptile209 heeft alleen geen idee waar dit nuttig voor is, want het bestand zal 10 tegen 1 niet meer werken als voorheen. .
Misschien wil je wat concreter aangeven wat je aan het doen bent, en vooral wat voor soort bestand je aan het bewerken bent? (XML, EXE, TXT, DOC, XLS, ...)

[RobIII]

Verwijderd schreef op maandag 16 augustus 2010 @ 14:44:
[...]

Dat ligt eraan hoe je je offset wilt representeren

Doorgaans in bytes (of een veelvoud daarvan als words etc.) Je kunt een halve byte niet schrijven (Ja, wel wijzigen met wat bitwise operaties maar daar hebben we het nu niet over).

Reptile209 schreef op maandag 16 augustus 2010 @ 14:45:
* Reptile209 heeft alleen geen idee waar dit nuttig voor is, want het bestand zal 10 tegen 1 niet meer werken als voorheen. .

Zolang het een .txt is ofzo (en daar heeft TS het over in zijn topicstart) valt het wel mee; bij binaries en andere formaten wordt het al lastiger of onmogelijk idd.

[ Voor 44% gewijzigd door RobIII op 16-08-2010 14:48 ]

[Mini-me]

Arcane Apex schreef op maandag 16 augustus 2010 @ 14:18:
Voor een CS project dien ik te weten hoe men de offset van een hexadecimale pair kan uitlezen en tevens hoe men een bepaalde hexadecimale pair een specifieke offset kan geven.

Betekent "CS" toevallig "Computer Science"? Je zou dan op zijn minst het probleem helder moeten kunnen beschrijven .

[EddoH]

Het begint me een beetje te dagen wat je bedoeld, maar je verdiend wel een prijs voor de categorie 'vaag omschrijven'


Ten eerste: offsets zijn geen waarden opzich. Je hoeft ze niet te veranderen.
Als je in een HEX-editor een file bekijkt, geeft de betreffende viewer alleen maar aan waar de verschillende bytes staan, ten opzichte van de start van de file (offset 0x00).
Wil je dus de 'offset' veranderen, betekent dit gewoon dat je de positie van de byte verplaatst. Oftewel: er komt iets anders te staan tussen de start en de betreffende byte: er bestaat geen 'leegte' tussen de bytes.

Zoals gvdh enRobll zegt. Je wilt 0-en invoegen in een bestand, waardoor de 'offset' van de tekst veranderd.

- Bestand lezen -> buffer
- Gedeelte van origineel tot plaats waar je wilt invoegen in 2e buffer schrijven.
- 0 -en invoegen in 2e buffer
- rest van origineel uit 1e buffer in 2e buffer zetten
- 2e buffer wegschrijven.

[Reptile209]

RobIII schreef op maandag 16 augustus 2010 @ 14:45:
[...]
Zolang het een .txt is ofzo (en daar heeft TS het over in zijn topicstart) valt het wel mee; bij binaries en andere formaten wordt het al lastiger of onmogelijk idd.

Nah, het gebruik van "stel" doet me het ergste vrezen . Voor hetzelfde geld probeert TS literal strings in een binary aan te passen (en komt daarbij ruimte tekort)...

Edit: @RobIII hieronder, dat bedoel ik precies, dat is ongeveer de zekerste manier om een binary om zeep te helpen door zaken te gaan verschuiven .

[ Voor 14% gewijzigd door Reptile209 op 16-08-2010 14:55 ]

[RobIII]

Reptile209 schreef op maandag 16 augustus 2010 @ 14:48: Voor hetzelfde geld probeert TS literal strings in een binary aan te passen (en komt daarbij ruimte tekort)...

Ruimte tekort is wel je minste probleem. Je hebt dan geen benul of je in data of code zit te wroeten, en als je in code ligt te poeren zullen allerlei vervelende zaken kunnen gebeuren. En als je in data ligt te poeren ook

[Arcane Apex]

Ok, laat het anders proberen uit te leggen. Stel je een hard disk platter voor. Op die platter zie je op microscopisch nivea een putje, of juist geen putje(vlakje). Een combinatie van 8 putjes en vlakjes creeert 1 byte.

Elk van die bytes heeft een fysieke locatie op de schijf, een absoluut adres als het ware. Om zaken te versimpelen hoeft men enkel het absolute adres van de eerste byte te weten en de rest van de byte stream kan uitgelezen worden met behulp van relatieve adressen, oftewel offsets.

Stel men heeft 2 bytes achter elkaar welke "ha" in ASCII voorstellen. Het enige wat ik wil doen is de 2e byte, dus de "a" een stukje verderop schuiven op de platter. Het fysieke absolute adres verandert dan en de bedoeling is dan tevens dat de offset ook hoger wordt. De volgorde blijft hetzelfde, alleen de plek van de byte op de schijf verandert, deze komt enkel verder te staan op de platter, that's it. Ik wil graag weten hoe ik de adressen van die bytes op de platter kan lezen en schrijven. Het liefst zowels de absolute adressen alswel de relatieve adressen, dus de offsets.

[Verwijderd]

Let wel dat als je 0-bytes gaat schrijven midden in een file dat string functies hier dan op stuk lopen want een 0-byte representeert het einde van een string (in C++ dan).

[ Voor 3% gewijzigd door Verwijderd op 16-08-2010 14:51 ]

[RobIII]

Arcane Apex schreef op maandag 16 augustus 2010 @ 14:51:
Het fysieke absolute adres verandert dan

En daardoor dus OOK de offset. De offset is, nogmaals, niets meer dan de lokatie t.o.v. het begin.

Arcane Apex schreef op maandag 16 augustus 2010 @ 14:51:
Ik wil graag weten hoe ik de adressen van die bytes op de platter kan lezen en schrijven. Het liefst zowels de absolute adressen alswel de relatieve adressen, dus de offsets.

Een relatief adres is altijd te vertalen naar een absoluut adres.

Als op plek 389672 een file begint dan is de offset voor de eerste byte in die file 0. En 5 bytes verder is de offset 5 en dat vertaalt zich naar 389677. Hoe moeilijk is dat? Als op plek 389672 en de daarop volgende bytes "Hallo" staat dan staat op 389677 (==offset 5 van 389672) dus de "o"

[ Voor 25% gewijzigd door RobIII op 16-08-2010 14:55 ]

[Verwijderd]

Arcane Apex schreef op maandag 16 augustus 2010 @ 14:51:
Ok, laat het anders proberen uit te leggen. Stel je een hard disk platter voor. Op die platter zie je op microscopisch nivea een putje, of juist geen putje(vlakje). Een combinatie van 8 putjes en vlakjes creeert 1 byte.

Elk van die bytes heeft een fysieke locatie op de schijf, een absoluut adres als het ware. Om zaken te versimpelen hoeft men enkel het absolute adres van de eerste byte te weten en de rest van de byte stream kan uitgelezen worden met behulp van relatieve adressen, oftewel offsets.

Stel men heeft 2 bytes achter elkaar welke "ha" in ASCII voorstellen. Het enige wat ik wil doen is de 2e byte, dus de "a" een stukje verderop schuiven op de platter. Het fysieke absolute adres verandert dan en de bedoeling is dan tevens dat de offset ook hoger wordt. De volgorde blijft hetzelfde, alleen de plek van de byte op de schijf verandert, deze komt enkel verder te staan op de platter, that's it. Ik wil graag weten hoe ik de adressen van die bytes op de platter kan lezen en schrijven. Het liefst zowels de absolute adressen alswel de relatieve adressen, dus de offsets.

Je snapt het echt niet he? Een locatie/adres is. Je kan die niet veranderen, je kan alleen de data op die locatie veranderen. Door data op punt A weg te halen en op punt B te schrijven bewerk je dat de offset van de data wijzigt. Je kan niet water van je gootsteen naar je badkuip verplaatsen door de locatie ervan te "editen", je verwijderd het uit je gootsteen (bijv. emmer) en giet het in je badkuip.

@RobIII: TS bedoeld moet offset de relatieve offset t.o.v. het begin van de datareeks.

[Verwijderd]

Ehmm.. wellicht probeert ie iets in de MBR (of filetables) te sleutelen?

[ Voor 12% gewijzigd door Verwijderd op 16-08-2010 14:57 ]

[Verwijderd]

Arcane Apex schreef op maandag 16 augustus 2010 @ 14:51:
Ok, laat het anders proberen uit te leggen. Stel je een hard disk platter voor. Op die platter zie je op microscopisch nivea een putje, of juist geen putje(vlakje). Een combinatie van 8 putjes en vlakjes creeert 1 byte.

Elk van die bytes heeft een fysieke locatie op de schijf, een absoluut adres als het ware. Om zaken te versimpelen hoeft men enkel het absolute adres van de eerste byte te weten en de rest van de byte stream kan uitgelezen worden met behulp van relatieve adressen, oftewel offsets.

Stel men heeft 2 bytes achter elkaar welke "ha" in ASCII voorstellen. Het enige wat ik wil doen is de 2e byte, dus de "a" een stukje verderop schuiven op de platter. Het fysieke absolute adres verandert dan en de bedoeling is dan tevens dat de offset ook hoger wordt. De volgorde blijft hetzelfde, alleen de plek van de byte op de schijf verandert, deze komt enkel verder te staan op de platter, that's it. Ik wil graag weten hoe ik de adressen van die bytes op de platter kan lezen en schrijven. Het liefst zowels de absolute adressen alswel de relatieve adressen, dus de offsets.

Er staan geen offsets op disk. Het wordt als 1 stream opgeslagen. Het zou ook wel een mooie boel worden als je voor elke byte ook een offset zou moeten opslaan, dan is je hardeschijf opeens 2x zo klein. Als het bestand gesplit moet worden omdat er anders geen ruimte voor is dan kun je de adressen hiervoor achterhalen in de betreffende inode (bij het ext bestandssysteem that is), maar dit is bestandssysteem specifiek.

[RobIII]

Verwijderd schreef op maandag 16 augustus 2010 @ 14:54:

@RobIII: TS bedoeld moet offset de relatieve offset t.o.v. het begin van de datareeks.

Dat zeg ik toch steeds? Een offset is een positie t.o.v. een andere positie. Of je daar nou begin van een file voor kiest of adres "0" van je "platter" boeit niet. (ik hanteer even de "begrippen" van de TS )

Als X een absoluut adres is dan is in X + Y de Y de offset. En in X - Y overigens ook; alleen heb je dan een negatieve offset. En of X nou het begin van een file is op adres 329339 of dat X het adres "0" van je "platter" is... boeie. Alleen, als je 329340 wil benaderen dan is in het eerste geval de offset 1 en in het tweede geval 329340.

[ Voor 33% gewijzigd door RobIII op 16-08-2010 14:59 ]

[EddoH]

Het filesysteem regelt waar wat op de schrijf wordt gezet.
Voor alles buiten het filesysteem lijkt het alsof files sequentieel op de schijf staan.
Daarom kun je de offset van bytes in een file NIET (!!!!!) veranderen. In theorie hoogstens de plaats op de fysieke schijf, maar daar moet je niet in gaan roeren.
Volgens mij wil je its met de partitionering van de schijf doen ofzo? Ik heb alleen geen flauw idee waarom.

[.oisyn]

Arcane Apex schreef op maandag 16 augustus 2010 @ 14:51:
Stel men heeft 2 bytes achter elkaar welke "ha" in ASCII voorstellen. Het enige wat ik wil doen is de 2e byte, dus de "a" een stukje verderop schuiven op de platter. Het fysieke absolute adres verandert dan en de bedoeling is dan tevens dat de offset ook hoger wordt. De volgorde blijft hetzelfde, alleen de plek van de byte op de schijf verandert, deze komt enkel verder te staan op de platter, that's it.

Je kunt 'm wel verder op de platter zetten, maar ertussen staan dan ook nog bytes. Wat moeten de waarden van die bytes worden?

[Reptile209]

Je wil dus de volgende aanpassing in een file maken:

...HALLO......
...H...ALLO...

Waarbij op de plaats van de puntjes ongedefinieerde data staat. Klopt dat zo'n beetje? En als je nou zonder het woord 'stel' te gebruiken zou moeten omschrijven wat je precies wil bereiken, wat is dat dan? Geef eens een heel concreet voorbeeld, dat doet wonderen.

[jelmervos]

Misschien moet de TS eerst maar es uitleggen wat hij wil bereiken. Daarna een oplossing bedenken.

[Verwijderd]

Ik begin het te begrijpen. Hij wil iets maken vergelijkbaar met de CHKDISK dat bad-sectors opspoorde. Dus aanpassingen doen in je FAT zodat een reeks "bits" op je schijf niet worden gebruikt.

File content: ABCDEFG

FAT:
voorbeeld.txt
Offset: 00-02
Offset: 04-08

resultaat: AB_CDEFG op je schijf, ABCDEFG in je file
(en sector/offset 3 vrij/badsectormarker/whatever)

[Arcane Apex]

RobIII schreef op maandag 16 augustus 2010 @ 14:52:
[...]

En daardoor dus OOK de offset. De offset is, nogmaals, niets meer dan de lokatie t.o.v. het begin.


[...]

Een relatief adres is altijd te vertalen naar een absoluut adres.

Als op plek 389672 een file begint dan is de offset voor de eerste byte in die file 0. En 5 bytes verder is de offset 5 en dat vertaalt zich naar 389677. Hoe moeilijk is dat?

Ik denk dat het probleem is zoals eerder in de thread aangegeven werd, dat offsets nergens op de schijf opgeslagen worden en dus altijd vanaf de eerste byte "gerekend" worden. Dat begrijp ik, echter wat ik wil is een byte "verplaatsen". De byte dient een "jump" te maken naar een andere(verdere) fysieke locatie op de platter, zodat de volgorde van de letters gewaarborgt blijft in het .txt bestand, maar de absolute adressen veranderen. Deze jumps dienen erg specifiek te zijn. Er komt dan dus een afstand te zitten tussen de bytes, maar ik wil de bytes van mijn file, welke het woord "hallo" in ASCII weergeven wel weer kunnen uitlezen en ook de afstanden tussen de bytes kunnen bepalen. Ik meende dit te kunnen doen door de offsets te veranderen, maar als het niet kan dan zal ik een andere manier moeten vinden.

[Verwijderd]

Het principe wat je beschrijft kan. Noem het in vredesnaam geen "offsets veranderen". Wat je wilt is je File Allocation Table manipuleren. Dit is mogelijk maar bijzonder gevaarlijk. Mag ik vragen waarom je dit wilt?


dit is de info die je zoekt: http://www.pjrc.com/tech/8051/ide/fat32.html (of althans de theorie)

[ Voor 19% gewijzigd door Verwijderd op 16-08-2010 15:11 ]

[EddoH]

Ok....maar wat wil je nou eigenlijk echt doen? Wat is je preciese doel?
Bytes verplaatsen op een harde schijf is geen doel op zich?
We willen je graag helpen, maar dan moeten we wel weten wat je nou wilt bereiken...

[Verwijderd]

Arcane Apex schreef op maandag 16 augustus 2010 @ 15:07:
[...]


Ik denk dat het probleem is zoals eerder in de thread aangegeven werd, dat offsets nergens op de schijf opgeslagen worden en dus altijd vanaf de eerste byte "gerekend" worden. Dat begrijp ik, echter wat ik wil is een byte "verplaatsen". De byte dient een "jump" te maken naar een andere(verdere) fysieke locatie op de platter, zodat de volgorde van de letters gewaarborgt blijft in het .txt bestand, maar de absolute adressen veranderen. Deze jumps dienen erg specifiek te zijn. Er komt dan dus een afstand te zitten tussen de bytes, maar ik wil de bytes van mijn file, welke het woord "hallo" in ASCII weergeven wel weer kunnen uitlezen en ook de afstanden tussen de bytes kunnen bepalen. Ik meende dit te kunnen doen door de offsets te veranderen, maar als het niet kan dan zal ik een andere manier moeten vinden.

Aha nu begin ik het te snappen. Wat je hiervoor moet doen is bestandssysteem specifiek. Over welk bestandsyssteem hebben we het hier? FAT, EXT, ZFS, UFS? De bedoeling is dan dat je de lengte van de stream aanpast in de bijpassende file descriptor (inodes bij EXT). Vervolgens moet je er een entry bij schrijven met het nieuwe absolute adres van het stuk wat je hebt opgeschoven, samen met de lengte van het nieuwe stuk.

Oja dit is natuurlijk wel heel globaal. Er komt nog wel iets meer bij kijken.

[RobIII]

Verwijderd schreef op maandag 16 augustus 2010 @ 15:14:
[...]


Aha nu begin ik het te snappen. Wat je hiervoor moet doen is bestandssysteem specifiek. Over welk bestandsyssteem hebben we het hier? FAT, EXT, ZFS, UFS? De bedoeling is dan dat je de lengte van de stream aanpast in de bijpassende file descriptor (inodes bij EXT). Vervolgens moet je er een entry bij schrijven met het nieuwe absolute adres van het stuk wat je hebt opgeschoven, samen met de lengte van het nieuwe stuk.

En hou er ook rekening mee dat je altijd hele blokken zult schrijven van X bytes. Losse bytes is, AFAIK althans, onder geen enkel FS mogelijk.

[.oisyn]

Probeer eerst eens uit te leggen waarom je dit wilt, want ik kan geen enkel zinnig probleem bedenken waarbij dit de oplossing is. Daarnaast werkt het idd alleen met veelvouden van bytes (meestal 4096, maar afhankelijk van je filesystem en configuratie), dus in je "hallo" voorbeeld moet de "h" op n*4096-1 staan en de "a" op n*4096

[ Voor 10% gewijzigd door .oisyn op 16-08-2010 15:23 ]

[Janoz]

Wat de topicstarter wil kan theoretisch wel, maar dan moet hij de blocksize van zijn HD even instellen op 1 byte. Dat de FAT in dat geval zo ongeveer zijn complete schijfruimte inneemt is dan iets dat hij maar op de koop toe moet nemen.

[RobIII]

Janoz schreef op maandag 16 augustus 2010 @ 15:31:
Wat de topicstarter wil kan theoretisch wel, maar dan moet hij de blocksize van zijn HD even instellen op 1 byte. Dat de FAT in dat geval zo ongeveer zijn complete schijfruimte inneemt is dan iets dat hij maar op de koop toe moet nemen.

Lijkt me, ook theoretisch, onmogelijk. Je hebt altijd meer dan 1 byte "administratie" in je FAT per block. Dus als je blokcksize 1 wordt heb je meer administratie dan bytes Ik kan zo snel geen harde gegevens vinden maar 512 bytes is volgens mij het minimum in FAT32 (maar goed, een block zou theoretisch wellicht best 64 bytes kunnen zijn ofzo).

[ Voor 14% gewijzigd door RobIII op 16-08-2010 15:37 ]

[Verwijderd]

Zolang het data is kan alles. Al is de blocksize nog zo groot: data is te manipuleren.

De reden dat er bijna geen voorbeelden over te vinden zijn is dat het gevaarlijk is voor je data. Ik wil er best eens naar kijken maar dan wil ik wel weten waarom...

[Arcane Apex]

EddoH schreef op maandag 16 augustus 2010 @ 14:59:
Het filesysteem regelt waar wat op de schrijf wordt gezet.
Voor alles buiten het filesysteem lijkt het alsof files sequentieel op de schijf staan.
Daarom kun je de offset van bytes in een file NIET (!!!!!) veranderen. In theorie hoogstens de plaats op de fysieke schijf, maar daar moet je niet in gaan roeren.

Wroeten in het filesysteem is dus wellicht exact wat ik wil doen. Het probleem is dat elk filesysteem anders is. Wanneer er een "real world" applicatie geschreven zou moeten worden welke doet wat ik wil, dan zou ik dus voor elk type filesysteem andere code moeten schrijven, wat erg complex zou zijn.

Reptile209 schreef op maandag 16 augustus 2010 @ 15:00:
Je wil dus de volgende aanpassing in een file maken:

...HALLO......
...H...ALLO...

Waarbij op de plaats van de puntjes ongedefinieerde data staat. Klopt dat zo'n beetje? En als je nou zonder het woord 'stel' te gebruiken zou moeten omschrijven wat je precies wil bereiken, wat is dat dan? Geef eens een heel concreet voorbeeld, dat doet wonderen.

Als Computer Science opdracht hebben we voor het vak compressie een opdracht/raadsel gekregen van de leraar. Dat raadsel dient dus opgelost te worden en is alsvolgt:

Bedenk een (compressie en decompressie)algoritme voor een .txt bestand met de oorspronkelijke inhoud van 15x8-bits (zie onder). Zorg dat het resultaat in 5x8-bits opgeslagen kan worden en het woord "hallo" vormt in een nieuw tekstbestand. 1/3e van de inhoud van het oorspronkelijke bestand blijft dus over in het nieuwe bestand. Maar nu! Zorg er tevens voor dat je je bestand kan decomprimeren naar het oorspronkelijke bestand. Het compressie en decompressie algoritme dient tevens te kunnen werken voor andere woorden welke opgebouwd zijn uit karakters met 1 of meerdere spaties ertussen. Dus elk woord dat men typt in het oorspronkelijke bestand, onafhankelijk van het aantal spaties tussen de karakters, dient te kunnen worden gecomprimeerd naar een bestand met enkel het woord zonder de spaties tussen de karakters. Maar vanuit dat gecomprimeerde bestand moet men ook kunnen decomprimeren naar het originele bestand met het correct aantal spaties tussen de karakters van het woord. Het doel is optimalisatie van de bestandsgrootte.
Hint: Je zult het aantal spaties voor elk karakter dus ergens kwijt moeten, terwijl je toch de inhoud van het bestand terugbrengt naar 1/3e van het origineel!

Dit is het oorspronkelijk bestand dat we moeten comprimeren. Het toont het woord "h a l l o" met een aantal spaties tussen de karakters.

code:

68 20 20 61 20 6C 20 20 20 6C 20 20 20 20 6F

Dit moet het resultaat worden: "hallo"

code:

68 61 6C 6C 6F

Het klinkt als een vreemde opdracht, maar het doel is dus optimalisatie van bestandsgrootte op een specifieke manier. Mijn eerste intuitie was om de spaties op te slaan in verschillen in de offset, maar dat kan dus niet. Toen dacht ik, ok dan kan ik het aantal spaties voor elk karakter dus misschien opslaan door bytes een aantal adressen "verder" te laten jumpen. Dus als er 3 spaties staan voor een karakter, dan laat ik de byte van het karakter dus 3 bytes verder opslaan op de platter, zo kan ik relatief bepalen hoeveel spaties er tussen de karakters stond, terwijl de spaties ansich uit de inhoud van het tekstbestand verwijderd kunnen worden. Mijn decompressie algoritme zou dan kijken naar de afstand tussen de adressen van de karakters en daaruit dan weer opmaken hoeveel spaties er stonden tussen elk karater.

[jelmervos]

Er wordt nergens in de opdracht gesproken over de bestandsnaam, die kun je dus misbruiken. Sla in de bestandsnaam gewoon de locaties en lengtes van de spaties op.

[RobIII]

Ik zou als ik jou was nog eens de boeken in duiken en gewoon gaan uitvogelen wat compressie precies inhoudt / doet.
1 ding is zeker: je bent in (waaaaaaaaaaaaaaaaay) de verkeerde richting aan 't denken.

[ Voor 28% gewijzigd door RobIII op 16-08-2010 15:47 ]

[Verwijderd]

Voor deze opdracht?: Blijf af van de filesystem. Niet aan beginnen, niet doen. Genoeg andere opties om het "probleem" op te lossen.

[Arcane Apex]

RobIII schreef op maandag 16 augustus 2010 @ 15:46:
Ik zou als ik jou was nog eens de boeken in duiken en gewoon gaan uitvogelen wat compressie precies inhoudt / doet.
1 ding is zeker: je bent in (waaaaaaaaaaaaaaaaay) de verkeerde richting aan 't denken.

Het doel is optimalisatie van de bestandsgrootte. Ik gebruikte weliswaar de termen compressie en decompressie, maar dat is omdat we het voor het vak "compressie" doen. Optimalisatie is daar een onderdeel van.

[EddoH]

Optimalisatie van bestandsgrootte == compressie.

Je zou een mini dictionary kunnen maken van de 5 karakters, dit kan je opslaan in 4 bits. Dan iets van RLE erover. Kom je al een eind.

[Arcane Apex]

Verwijderd schreef op maandag 16 augustus 2010 @ 15:47:
Voor deze opdracht?: Blijf af van de filesystem. Niet aan beginnen, niet doen. Genoeg andere opties om het "probleem" op te lossen.

Echter zie ik dan niet in hoe ik precies het aantal bytes van het .txt bestand kan terugbrengen op de platter.
Iemand in de collegezaal opperde al dat men de filenaam en attributes van het .txt bestand zou kunnen gebruiken om het op te lossen. Waarop de leraar zei: "Als je dat zou doen zou je een regel van de opdracht overtreden, omdat wanneer ik jou een .txt bestand met een inhoud van 100MB aan tekst zou geven, dan zou je niet alles in de bestandsnaam en de attributes kwijt kunnen. De bedoeling is dus dat het voor elke reeks aan karakters en woorden moet kunnen werken, ongeacht de grootte van de inhoud van het bestand

Wroeten in het filesysteem lijkt mij dus daarom het meest plausibele.

[Verwijderd]

dus samengevat:

je hebt een uncompressed file met de text 'hallo' en verder alleen maar spaties (15 bytes in totaal).
Nu moet je een compressiefunctie maken die je file van 15 bytes terugbrengt naar 5 en daarbij ook een decompressiefunctie om de orginele inhoud weer te tonen?

Hierbij maakt het dus niet uit wat de gecomprimeerde (geoptimaliseerde) vorm is?

(edit: overigens moet je wel wat gaan doen aan je "probleem uitleg". We blijven telkens gokken naar randvoorwaarden die jij al weet maar ons niet verteld)

[ Voor 17% gewijzigd door Verwijderd op 16-08-2010 15:57 ]

[Verwijderd]

Arcane Apex schreef op maandag 16 augustus 2010 @ 15:42:
[...]
Hint: Je zult het aantal spaties voor elk karakter dus ergens kwijt moete, terwijl je toch de inhoud van het bestand terugbrengt naar 1/3e van het origineel!

Wat je dus wilt is de informatie van een letter met tot N spaties samen opslaan in 8 bit, als je bedenkt dat er slechts 26 letters zijn en een byte 256 "tekens" kan bevatten, dan betekent dit dus dat een byte een "overhead" aan bits bevat die niet gebruikt worden mits je weet dat er alleen letters voorkomen.

Blijf van het filesystem af! De opdracht heeft het niet eens over files, maar over een reeks karakters die in een bytestring gevat zijn. Dat die toevalligerwijs in een file staan moet voor jou geen effect hebben op je aanpak.

[ Voor 15% gewijzigd door Verwijderd op 16-08-2010 15:57 ]

[Arcane Apex]

Verwijderd schreef op maandag 16 augustus 2010 @ 15:55:
dus samengevat:

je hebt een uncompressed file met de text 'hallo' en verder alleen maar spaties (15 bytes in totaal).
Nu moet je een compressiefunctie maken die je file van 15 bytes terugbrengt naar 5 en daarbij ook een decompressiefunctie om de orginele inhoud weer te tonen?

Hierbij maakt het dus niet uit wat de gecomprimeerde (geoptimaliseerde) vorm is?

Juist, behalve dan dat het woord hallo(zonder spaties) het resultaat is van de geoptimaliseerde vorm. Maar de leraar heeft dus een mechanisme in de opdracht ingebouwd, zodat studenten niet kunnen cheaten. Want je algoritme zou voor elke bestandsgrootte moeten kunnen werken en voor alle karakters uit de ASCII karakter set. (was dat vergeten te vertellen meen ik)

Dus een hack waarbij de bestandsnaam en de bestandsattributen gebruikt worden zou dus een overtreding zijn van de regels.

[ Voor 12% gewijzigd door Arcane Apex op 16-08-2010 16:02 ]

[Verwijderd]

@ ^^^:

EddoH schreef op maandag 16 augustus 2010 @ 15:53:
Optimalisatie van bestandsgrootte == compressie.

Je zou een mini dictionary kunnen maken van de 5 karakters, dit kan je opslaan in 4 bits. Dan iets van RLE erover. Kom je al een eind.

Als alle mogelijke waarden in een byte kunnen zitten (wat nergens uit de oprachtomschrijving blijkt overigens) moet je een oplossing als EddoH noemt gebruiken. Ik kan me overigens niet voorstellen dat je een dergelijke opdracht krijgt zonder dat de oplossing je zowat in het boek/dictaat/les wordt toegereken...

[jmzeeman]

laat maar

[ Voor 86% gewijzigd door jmzeeman op 16-08-2010 16:03 ]

[Verwijderd]

Arcane Apex schreef op maandag 16 augustus 2010 @ 15:59:
[...]
Want je algoritme zou voor elke bestandsgrootte moeten kunnen werken en voor alle karakters uit de ASCII karakter set. (was dat vergeten te vertellen meen ik)

Dat is best wel belangrijk.

Dus het formaat van het oorspronkelijke bestand staat niet vast en de inhoud kunnen dus alle ASCII karakters zijn..... ehmmmm...... weet je dat heel zeker?

[Arcane Apex]

jmzeeman schreef op maandag 16 augustus 2010 @ 16:02:
Hint: ASCII is 7-bit

Extended ASCII is 8-bits en die kunnen tevens voorkomen in een tekstbestand.

[Verwijderd]

jmzeeman schreef op maandag 16 augustus 2010 @ 16:02:
Hint: ASCII is 7-bit

Hint: het alfabet is minder dan 5 bit.

BTW: je opdrachtomschrijving klopt niet. Ik weet niet hoe het precies genoemd is in je les, maar zoals het er nu staat kan het nooit kloppen. Je beweerd namelijk dat het resultaat van de compressie altijd "hallo" is, ongeacht de invoer, terwijl na decompressie het resultaat wel weer moet kloppen.
Moet er nou een woord of een willekeurige reeks bytes gecomprimeerd kunnen worden....

[ Voor 8% gewijzigd door Verwijderd op 16-08-2010 16:05 ]

[Arcane Apex]

Verwijderd schreef op maandag 16 augustus 2010 @ 16:03:
[...]


Dat is best wel belangrijk.

Dus het formaat van het oorspronkelijke bestand staat niet vast en de inhoud kunnen dus alle ASCII karakters zijn..... ehmmmm...... weet je dat heel zeker?

Ja dat weet ik zeker. De leraar vertelde tevens dat men rekening diende te houden met de extended ASCII karakter set, omdat die ook gewoon in een tekstbestand voor kunnen komen, wat de opdracht nog pittiger maakt, omdat er een bit toegevoegd wordt per karakter.

Hierdoor vermoed ik dus dat de oplossing in de adressering ligt in het filesystem, maar zeker weten doe ik het niet.

[ Voor 14% gewijzigd door Arcane Apex op 16-08-2010 16:07 ]

[EddoH]

Als ik de opdrachtomschrijving lees (specifiek de 'HINT') denk ik dat je leraar bedoelde dat het voor het gehele alfabet toepasbaar moet zijn. Niet de gehele ASCII karakterset. Anders is de opdracht namelijk onmogelijk bij zo'n klein bestand.......

edit: dus ook extended ASCII set? ... Dan vind ik 15 karakters opslaan in 5 bytes best knap...

[ Voor 17% gewijzigd door EddoH op 16-08-2010 16:11 ]

[Verwijderd]

Arcane Apex schreef op maandag 16 augustus 2010 @ 16:05:
[...]


Ja dat weet ik zeker. De leraar vertelde tevens dat men rekening diende te houden met de extended ASCII karakter set, omdat die ook gewoon in een tekstbestand voor kunnen komen, wat de opdracht nog pittiger maakt, omdat er een bit toegevoegd wordt per karakter.

Hier weer: quote je leraar i.p.v. je eigen interpretatie te geven.

Als je rekening moet houden met de extended ascii set kan dat ook betekenen dat een woord uit het alfabet opgebouwd is uit bytes van 8 i.p.v. 7 bit, het zegt niets over welke tekens kunnen/mogen voorkomen.

Ik kan je nu al op een briefje geven dat de opdracht volgens jouw omschrijving onmogelijk is, terwijl dat vast niet de bedoeling is geweest van je leraar. Je zegt namelijk feitelijk:
"een willekeurige reeks bytes moet tot 1/3e kunnen worden gecompressed zonder gebruikmaking van enige kennis van de inhoud"
Sorry, gaat nie lukke nie.

[Arcane Apex]

Verwijderd schreef op maandag 16 augustus 2010 @ 16:05:
[...]

Hint: het alfabet is minder dan 5 bit.

BTW: je opdrachtomschrijving klopt niet. Ik weet niet hoe het precies genoemd is in je les, maar zoals het er nu staat kan het nooit kloppen. Je beweerd namelijk dat het resultaat van de compressie altijd "hallo" is, ongeacht de invoer, terwijl na decompressie het resultaat wel weer moet kloppen.
Moet er nou een woord of een willekeurige reeks bytes gecomprimeerd kunnen worden....

Voor de opdracht hebben we het woord hallo met een aantal spaties als voorbeeld gekregen, maar de optimalisatie en de-optimalisatie moet dus kunnen werken voor elk karakter uit de ASCII set en Extended ASCII set. Wat neer komt op 8-bits per karakter dus.

[Verwijderd]

Arcane Apex schreef op maandag 16 augustus 2010 @ 16:05:
[...]
Ja dat weet ik zeker. De leraar vertelde tevens dat men rekening diende te houden met de extended ASCII karakter set, omdat die ook gewoon in een tekstbestand voor kunnen komen, wat de opdracht nog pittiger maakt, omdat er een bit toegevoegd wordt per karakter.

Hierdoor vermoed ik dus dat de oplossing in de adressering ligt in het filesystem, maar zeker weten doe ik het niet.

Dus je moet simpelweg 33% kleiner.

mbt je filesystem: elke "jump" in je filetable zijn ook bytes. Als daarin de oplossing zou liggen zal daar ook naar gekeken worden. Ik heb ooit wel eens wat gedaan met filetables maar hierin zit niet de oplossing.

[Verwijderd]

Arcane Apex schreef op maandag 16 augustus 2010 @ 16:05:
[...]
Hierdoor vermoed ik dus dat de oplossing in de adressering ligt in het filesystem, maar zeker weten doe ik het niet.

Maar dan cheat je, de addressering maakt in jouw denken namelijk deel uit van de informatie en moet dus opgeslagen worden. Je kan natuurlijk wel telkens een byte/letter (volgens jou hetzelfde) opslaan met erbij hoeveel verder de volgende letter ligt, maar dan kan je nooit of te nimmer alleen de letters overhouden. Je hebt immers die addressering nog, en die moet je opslaan, anders "maak" je informatie be decompressie (of je moet een vast patroon hebben van de spaties, bijvoorbeeld om en om 1 en 2 spaties)

[Arcane Apex]

Verwijderd schreef op maandag 16 augustus 2010 @ 16:10:
[...]

Dus je moet simpelweg 33% kleiner.

mbt je filesystem: elke "jump" in je filetable zijn ook bytes. Als daarin de oplossing zou liggen zal daar ook naar gekeken worden. Ik heb ooit wel eens wat gedaan met filetables maar hierin zit niet de oplossing.

Niet simpelweg naar 33% van het originele bestand. De originele betekenis(en dus volgorde van de letters van het woord hallo) dient gewaarborgt te blijven wanneer men het geoptimaliseerde bestand opent.

De spaties dienen dus te verdwijnen, maar niet onomkeerbaar. En dat terwijl men de inhoud van het bestand dus terugbrengt naar 1/3e van de oorsprongkelijke grootte.

[EddoH]

Je kan met een legio aan compressiemethoden 33% compressie halen. Maar niet met zo'n klein bestand. Er zal altijd een vorm van header / table / dictionary whatever aan toegevoegd moeten worden..
Een efficiency van 66% (15 ->5) met volledige Extended ASCII set bij 15 karakters geloof ik niet dat mogelijk is.

[Arcane Apex]

Er is altijd de mogelijkheid dat het een soort van strikvraag of strikopdracht is, maar dat vermoed ik niet. Ik denk dat de leraar wil dat we iets heel specifieks inzien mbt optimalisatie.

De opdracht is dan ook heel specifiek afgebakend, waarschijnlijk zodat de studenten maar 1 richting op kunnen, maar welke richting dat is, daar ben ik niet zo zeker over.

Er zal voor dit soort optimalisatie wellicht een technische term bestaan, maar die is ons dan weer niet verteld, zodat we daar niet op kunnen Googlen.

[ Voor 46% gewijzigd door Arcane Apex op 16-08-2010 16:19 ]

[Verwijderd]

Arcane Apex schreef op maandag 16 augustus 2010 @ 16:14:
[...]
Niet simpelweg naar 33% van het originele bestand. De originele betekenis(en dus volgorde van de letters van het woord hallo) dient gewaarborgt te blijven wanneer men het geoptimaliseerde bestand opent.

De spaties dienen dus te verdwijnen, maar niet onomkeerbaar. En dat terwijl men de inhoud van het bestand dus terugbrengt naar 1/3e van de oorsprongkelijke grootte.

Gaat het om enkel de spaties die eruit moeten of maakt het niet uit?

ik krijg "abcdefghijklmnop" nooit naar 33% "<5xspatie>hallo<5xspatie>" is al een stuk makkelijker.

[Verwijderd]

Arcane Apex schreef op maandag 16 augustus 2010 @ 16:14:
[...]


Niet simpelweg naar 33% van het originele bestand. De originele betekenis(en dus volgorde van de letters van het woord hallo) dient gewaarborgt te blijven wanneer men het geoptimaliseerde bestand opent.

De spaties dienen dus te verdwijnen, maar niet onomkeerbaar. En dat terwijl men de inhoud van het bestand dus terugbrengt naar 1/3e van de oorsprongkelijke grootte.

Ik denk dat je je leraar niet geheel goed begrepen hebt. Vraag de opdracht niet eens na, want wat jij beweert kan simpelweg niet. We kunnen wel proberen te helpen, maar het blijft giswerk omdat met zekerheid je probleem niet overeenkomt met de opdracht van de leraar. zo vermoed ik dat je een woord hebt dat alleen het alfabet beslaat, dat het alleen spaties ertussen heeft, dat na decompressie het woord weer zijn originele vorm moet hebben en dat de compressie je beperkt tot 8 bit bytes.

[Verwijderd]

Arcane Apex schreef op maandag 16 augustus 2010 @ 16:17:
Er is altijd de mogelijkheid dat het een soort van strikvraag of strikopdracht is, maar dat vermoed ik niet. Ik denk dat de leraar wil dat we iets heel specifieks inzien mbt optimalisatie.

De opdracht is dan ook heel specifiek afgebakend, waarschijnlijk zodat de studenten maar 1 richting op kunnen, maar welke richting dat is, daar ben ik niet zo zeker over.

Er zal voor dit soort optimalisatie wellicht een technische term bestaan, maar die is ons dan weer niet verteld, zodat we daar niet op kunnen Googlen.

Zoals ik net zei: ik denk dat je de opdracht niet goed onthouden hebt, laat staan goed begrepen.

In deze situatie zou je kunnen zeggen: het patroon van spaties is 2-1-3-4. Je kan dus zeggen: het patroon is altijd tussen de eerste en tweede letter 2 spaties, tussen de tweede ende derde 1 spatie en daarna zoveel spaties als er letters aan vooraf gegaan zijn. Dit is gruwelijk lelijk en gaat dus ook niet werken, wat je feitelijk zegt is dat het patroon van spaties geheel voorspelbaar is en dus geen informatie bevat.
Dan kan je "h a l l o" wel degelijk opslaan als "hallo", en de spaties weglaten. Bij decompressie weer hetzelfde: 1e letter, 2 spaties, 2e letter, 1 spatie, 3e letter, 3 spaties..... n-de letter, n spaties.

[Arcane Apex]

Verwijderd schreef op maandag 16 augustus 2010 @ 16:18:
[...]

Ik denk dat je je leraar niet geheel goed begrepen hebt. Vraag de opdracht niet eens na, want wat jij beweert kan simpelweg niet. We kunnen wel proberen te helpen, maar het blijft giswerk omdat met zekerheid je probleem niet overeenkomt met de opdracht van de leraar.

Ik zal de leraar deze thread laten lezen om te kijken of ik de opdracht wel goed begrepen en/of uitgelegd heb, maar ik vermoed van wel, want we zijn 2 lesuren bezig geweest om de opdracht te doorlopen en zo'n beetje alles wat in deze thread aan bod is gekomen is ook in de les gezegd en gevraagd.

Zoals met veel dingen lijkt het wellicht ingewikkelder dan het uiteindelijk blijkt te zijn, maar dan moet men er maar net achter komen hoe de vork precies in de steel zit.

Er zullen waarschijnlijk legio compressie- en optimalisatie-algoritmen bestaan welke een tekstbestand kan ontdoen van z'n spaties en deze weer terug kan decomprimeren of de-optimaliseren naar het origineel met de spaties. Waarschijnlijk is het niet de eerste keer dat zoiets gedaan wordt, lijkt me. Wij moeten het dan wel op een hele specifieke manier doen, maar daar zal dan wel een reden voor zijn.

[ Voor 18% gewijzigd door Arcane Apex op 16-08-2010 16:32 ]

[Verwijderd]

even de data "hallo" naar decimaal

h 104
a 97
l 108
l 108
o 111


wat je kan opslaan =
byte1: 104 + spaties na deze letter (dus 114 = h + 10 spaties)
byte2: 97 + spaties na deze letter (dus 97 = a + 0 spaties)
etc

het aantal spaties voorafgaand aan de eerste letter = filesize - berekening van aantal karaters nu in gebruik


dit werkt alleen maar als je weet dat "hallo" de output moet zijn. Zodra je andere tekens gebruikt klopt je berekening niet meer.

[Reptile209]

Verwijderd schreef op maandag 16 augustus 2010 @ 16:31:
[...]
dit werkt alleen maar als je weet dat "hallo" de output moet zijn. Zodra je andere tekens gebruikt klopt je berekening niet meer.

Dus eigenlijk ben je dan op een heel erg inefficiënte manier het aantal spaties en hun positie aan het opslaan. Laat dan het hele 'hallo' achterwege en sla alleen je spatie-info op .

[Spiked]

Wordt er niet gewoon bedoeld dat een ascii bestand compressed opgeslagen moet worden zonder spaties, en weer decompressed kan worden naar het origineel?
Dat in het voorbeeld "68 20 20 61 20 6C 20 20 20 6C 20 20 20 20 6F" 10 spaties zitten, betekend niet dat wanneer er andere tekst voorbij komt, deze ook 1/3e van de grootte moet worden? De spaties moeten er alleen uit, of dat nou 66% of 10% kleiner is, maakt niet uit?

[!null]

Staat de opdracht niet ergens online zodat je de tekst hier naartoe kunt kopieren?

Het is me overigens een wonder hoe jij links legt. Er komt een bytereeks voor die ingepakt moet worden, je noemt het hex pairs en begint het vervolgens over het filesysteem. Gelukkig weten we nu op pagina 3 wel waar het over gaat.

Ik geloof ook niet dat het gecompresseerde resultaat letterlijk 5 ascii bytes in de vorm van 'hallo' kan zijn, want dan mist er simpelweg informatie.

[EddoH]

Spiked schreef op maandag 16 augustus 2010 @ 16:38:
Wordt er niet gewoon bedoeld dat een ascii bestand compressed opgeslagen moet worden zonder spaties, en weer decompressed kan worden naar het origineel?
Dat in het voorbeeld "68 20 20 61 20 6C 20 20 20 6C 20 20 20 20 6F" 10 spaties zitten, betekend niet dat wanneer er andere tekst voorbij komt, deze ook 1/3e van de grootte moet worden? De spaties moeten er alleen uit, of dat nou 66% of 10% kleiner is, maakt niet uit?

Dat maakt het nog steeds een naar mijn weten niet-oplosbaar probleem (met de gegeven eisen)

[ Voor 73% gewijzigd door EddoH op 16-08-2010 16:42 ]

[Killemov]

Modbreak:

Mensen afkraken, en op de man spelen is niet nodig!

Of je hebt het over lossless compressie, waarbij het origineel met spaties dus ooit weer gereconstrueerd moet worden of je hebt het over filtering waarbij het origineel na het proces niet meer relevant is.

Al het gaat om compressie heb je iets nodig dat metadata heet, ofwel data die je data beschrijft. Aangezien je die niet in je doelbestand opneemt ( hallo = 5 bytes ) moet je het ergens anders kwijt. (hardcoded of ander bestand?)

Als het puur gaat om het verkleinen van het bestand door het detecteren van spaties kun je een extra bitje introduceren dat aangeeft of de volgende acht bits de inhoud van een karakter representeren (1) of dat je een spatie invult en weer kijkt naar het volgende bit voor het volgende karakter (0).

De gebruikte dictionary bevat nu dus alleen een spatie. Dit is al een voorbeeld van metadata.

[ Voor 5% gewijzigd door Woy op 16-08-2010 17:42 ]

[Verwijderd]

Reptile209 schreef op maandag 16 augustus 2010 @ 16:35:
[...]
Dus eigenlijk ben je dan op een heel erg inefficiënte manier het aantal spaties en hun positie aan het opslaan. Laat dan het hele 'hallo' achterwege en sla alleen je spatie-info op .

Hahaha.... inderdaad. Nog niet eens aan gedacht, was compleex gefixeerd op het zo intact mogelijk laten van de orginele data

[Mini-me]

Mini-me schreef op maandag 16 augustus 2010 @ 14:45:
[...]

Betekent "CS" toevallig "Computer Science"? Je zou dan op zijn minst het probleem helder moeten kunnen beschrijven .

Ik maakte deze opmerking eerder om te kunnen inschatten voor welke opleiding je deze opdracht moet maken. Voor een lesje informatica op de middelbare school verwacht ik namelijk een iets meer voor de hand liggende oplossing dan voor een Master vak aan de universiteit. In welke context moet je dit probleem oplossen?

[Arcane Apex]

Spiked schreef op maandag 16 augustus 2010 @ 16:38:
Wordt er niet gewoon bedoeld dat een ascii bestand compressed opgeslagen moet worden zonder spaties, en weer decompressed kan worden naar het origineel?
Dat in het voorbeeld "68 20 20 61 20 6C 20 20 20 6C 20 20 20 20 6F" 10 spaties zitten, betekend niet dat wanneer er andere tekst voorbij komt, deze ook 1/3e van de grootte moet worden? De spaties moeten er alleen uit, of dat nou 66% of 10% kleiner is, maakt niet uit?

De spaties moeten er inderdaad gewoon tussenuit, maar het proces moet niet onomkeerbaar zijn.
Tevens dient men in het geoptimaliseerde bestand de tekst gewoon te kunnen lezen zonder de spaties.
Dus de volgorde van de karakters dient in het geoptimaliseerde bestand gewaarborgd te blijven.

De crux is dat er voor de spaties geen extra bits of bytes gebruikt mogen worden in het geoptimaliseerde bestand, vandaar dat ik dus dacht/denk dat de oplossing op de 1 of andere manier ligt in wellicht de afstand tussen de bytes en/of de adressering van de bytes. Men moet de data van die spaties toch ergens kwijt.

[Arcane Apex]

Mini-me schreef op maandag 16 augustus 2010 @ 16:47:
[...]


Ik maakte deze opmerking eerder om te kunnen inschatten voor welke opleiding je deze opdracht moet maken. Voor een lesje informatica op de middelbare school verwacht ik namelijk een iets meer voor de hand liggende oplossing dan voor een Master vak aan de universiteit. In welke context moet je dit probleem oplossen?

Op de opleiding Computer Science moeten we voor het vak compressie bestandsgroottes leren optimaliseren. Zoals je waarschijnlijk wel hebt gelezen dient dit op een hele specifieke manier te gebeuren waarbij we niet mogen cheaten en de opdracht dus heel specifiek afgebakend is. Het algoritme moet wel echt werken voor alle situaties, dus alle karakters van de ASCII set en Extended ASCII set.

Optimalisatie is 1 van de onderdelen van compressie.

[!null]

Het is dus geen eis dat de grote 33% moet zijn zoals sommige denken. Het moet gewoon als tekst leesbaar zijn, alleen zonder spaties.

Arcane Apex schreef op maandag 16 augustus 2010 @ 16:48:
[...]
De crux is dat er voor de spaties geen extra bits of bytes gebruikt mogen worden in het geoptimaliseerde bestand, vandaar dat ik dus dacht/denk dat de oplossing op de 1 of andere manier ligt in wellicht de afstand tussen de bytes en/of de adressering van de bytes. Men moet de data van die spaties toch ergens kwijt.

Wat ik me afvraag is of het een harde eis is dat er niks na de tekst komt. Met jou voorbeeld, als de uitkomst 5 bytes moet zijn met de waardes 'hallo' en daarachter mag niks meer komen, dan is die informatie er simpelweg niet. Die ben je dan verloren. Wellicht is het echter geen eis dat je geen info achter de tekst zonder spaties mag opslaan. Als je na de 'hallo' eindigt met een \0 dan stoppen tekst editors met lezen (hex editors niet natuurlijk) en kun je daarna spatie informatie opslaan.

Edit: Wellicht is het antwoord dat het niet kan, of dat het in het specefieke voorbeeld wel groter uitkomst dan het origineel. Misschien is deze opdracht puur om begrip te kweken over het onderwerp.

[ Voor 8% gewijzigd door !null op 16-08-2010 16:57 ]

[Verwijderd]

definieer leesbaar.....
(bepaalde karakters worden niet getoond als je zo ze op de commandline dumpt. Ze staan echter wil in het bestand. )

edit: ik ga naar huis. ben er morgen om 8:00 weer - ben benieuwd hoe dit afloopt

[ Voor 23% gewijzigd door Verwijderd op 16-08-2010 17:00 ]

[Verwijderd]

Arcane Apex schreef op maandag 16 augustus 2010 @ 16:48:
[...]


De spaties moeten er inderdaad gewoon tussenuit, maar het proces moet niet onomkeerbaar zijn.
Tevens dient men in het geoptimaliseerde bestand de tekst gewoon te kunnen lezen zonder de spaties.
Dus de volgorde van de karakters dient in het geoptimaliseerde bestand gewaarborgd te blijven.

*BEEP*

De crux is dat er voor de spaties geen extra bits of bytes gebruikt mogen worden in het geoptimaliseerde bestand,

*BEEP*

vandaar dat ik dus dacht/denk dat de oplossing op de 1 of andere manier ligt in wellicht de afstand tussen de bytes en/of de adressering van de bytes. Men moet de data van die spaties toch ergens kwijt.

Het moet niet onomkeerbaar zijn is niet hetzelfde als dat de volgorde onveranderd moet blijven en al helemaal niet dat het woord leesbaar moet zijn in de compressed variant.
Als je geen ruimte hebt om je spaties kwijt te kunnen dan zijn ze heel eenvoudig weg en onmogelijk te herconstrueren. Adressen zijn ook informatie en dus moet het ook opgeslagen worden en kost het dus ook ruimte, geen ontkomen aan.

Er zijn dus 2 oplossingen:
1) de compressed variant hoeft niet leesbaar te zijn en er is een beperking aan welke tekens voorkomen en hoeveel spaties er voorkomen.
2) je maakt een tweede bestand dat aangeeft hoeveel spaties er telkens tussen letters zitten.

[Verwijderd]

Arcane Apex schreef op maandag 16 augustus 2010 @ 16:53:
[...] Het algoritme moet wel echt werken voor alle situaties, dus alle karakters van de ASCII set en Extended ASCII set.

Wie zegt dat "alle situaties" betekent dat alle ASCII tekens kunnen voorkomen? Alle situaties kan ook duiden op alle willekeurige woorden van willekeurige lengte opgebouwd uit alfabetische karakters... En het lukt je niet om een bestand met "hallo" en tussen iedere letter 1 miljard spaties te reduceren tot 5 bytes.

[.oisyn]

3) je mag de bestandsnaam gebruiken om informatie in op te slaan.

[jmzeeman]

4) Je gebruikt quantum bogo sort decompress (compress is niet eens nodig, dit algoritme is zo geavanceerd dat elk willekeurig input bestand het goede antwoord geeft)

[Verwijderd]

Ik vermoed dat de opdracht meer luidt:
"ik heb een woord van alfabetische letters, gemengd met spaties. Ieder van deze tekens (letters/spaties) neemt 8 bit in, er is dus sprake van extended ASCII. Ontwikkel een algoritme om dit te comprimeren tot de lengte van het woord zonder de spaties, na decompressie moet het weer geheel leesbaar zijn. Er zitten maximaal zeven spaties tussen twee letters in."

Voor deze vraag kan je deze oplossing gebruiken:
"Beschrijf: a=0, b=1, c=2... z=25. Tel hierbij 32*spaties op, waarbij spaties het aantal spaties is dat op deze letter volgt. Schrijf vervolgens de ASCII representatie van dit getal weg."

Waar eerst 8 bits voor een letter en 8 bits voor een spatie werd gebruikt, worden nu 5 bits voor een letter en de overige 3 bits voor het aantal spaties gebruikt.

@oisyn: voor het gemak "vindt" ik dat een bestandsnaam ook een bestand is, alleen op een andere plek.

@jmzeeman: goed idee, nu nog een computer maken die het kan... en een universum maken waar zo'n computer kan bestaan...

[ Voor 12% gewijzigd door Verwijderd op 16-08-2010 17:07 ]

[Arcane Apex]

Verwijderd schreef op maandag 16 augustus 2010 @ 17:00:
[...]

Wie zegt dat "alle situaties" betekent dat alle ASCII tekens kunnen voorkomen? Alle situaties kan ook duiden op alle willekeurige woorden van willekeurige lengte opgebouwd uit alfabetische karakters... En het lukt je niet om een bestand met "hallo" en tussen iedere letter 1 miljard spaties te reduceren tot 5 bytes.

De leraar was vrij duidelijk over dat het alle karakters betreft in zowel de ASCII alswel Extended ASCII set. De term "alle situaties" gebruikte ik zelf om het uit te kunnen leggen, maar dat waren niet de exacte woorden van de leraar. Mijn excuses als het allemaal wat vaag overkomt.

[danslo]

Naieve implementatie en een beetje voorkauwen, maar was toch wel even leuk om m'n C kennis weer even naar boven te halen

[ Voor 18% gewijzigd door danslo op 16-08-2010 20:50 . Reden: pastebin expired ]

[Killemov]

Je kunt het vraagstuk filteren of lossless comprimeren niet onbeantwoord laten.

Arcane Apex schreef op maandag 16 augustus 2010 @ 16:48[/message]:
De spaties moeten er inderdaad gewoon tussenuit, maar het proces moet niet onomkeerbaar zijn.
Tevens dient men in het geoptimaliseerde bestand de tekst gewoon te kunnen lezen zonder de spaties.
Dus de volgorde van de karakters dient in het geoptimaliseerde bestand gewaarborgd te blijven.

... je hebt het over filteren.

Arcane Apex schreef op maandag 16 augustus 2010 @ 16:48[/message]:
De crux is dat er voor de spaties geen extra bits of bytes gebruikt mogen worden in het geoptimaliseerde bestand, vandaar dat ik dus dacht/denk dat de oplossing op de 1 of andere manier ligt in wellicht de afstand tussen de bytes en/of de adressering van de bytes. Men moet de data van die spaties toch ergens kwijt.

... je impliceert compressie.

[.oisyn]

Verwijderd schreef op maandag 16 augustus 2010 @ 17:05:
@oisyn: voor het gemak "vindt" ik dat een bestandsnaam ook een bestand is, alleen op een andere plek.

Prima dat jij dat vindt, maar de opdracht heeft het duidelijk over het minimaliseren van de bestandsgrootte van de .txt file. De bestandsnaam is niet per se 1:1 gekoppeld aan het bestand en telt al helemaal niet mee in de grootte van dat bestand in menig filesysteem.

[ Voor 18% gewijzigd door .oisyn op 16-08-2010 17:11 ]

[EddoH]

.oisyn schreef op maandag 16 augustus 2010 @ 17:10:
[...]

... maar de opdracht heeft het duidelijk.....

[Arcane Apex]

.oisyn schreef op maandag 16 augustus 2010 @ 17:01:
3) je mag de bestandsnaam gebruiken om informatie in op te slaan.

Daarmee zou dan wel een regel van de opdracht overtreden worden, want de leraar kan ons een 100MB .txt bestand gaan voorschotelen. Ik vermoed dat men nooit genoeg data in de bestandsnaam en zelfs bestandsattributen kwijt zal kunnen om de klus voor zo'n groot bestand te klaren.

[Verwijderd]

Arcane Apex schreef op maandag 16 augustus 2010 @ 17:08:
[...]


De leraar was vrij duidelijk over dat het alle karakters betreft in zowel de ASCII alswel Extended ASCII set. De term "alle situaties" gebruikte ik zelf om het uit te kunnen leggen, maar dat waren niet de exacte woorden van de leraar. Mijn excuses als het allemaal wat vaag overkomt.

Goed in dat geval: "Een willekeurige reeks bytes bevat een grote hoeveelheid 0x20 bytes. Maak een algoritme dat hierop compressie toepast. De efficientie is niet van belang."

In dit geval is de oplossing:
"Sla één 1-bit op, de volgende 8 bit (die dus over 2 bytes verdeeld is) bevatten een bytewaarde. Sla een 0-bit op, de volgende 8 bit (die dus over 2 bytes verdeeld is) bevatten het aantal 0x20 bytes. Combineer deze twee regels zodat het overeen komt met de gegeven input string."

Deze oplossing kan vrij eenvoudig grotere bestanden tot gevolg hebben dan het origineel en levert bovendien niets leesbaars op. Natuurlijk kan het een en ander gehusseld worden om de leesbaarheid te verbeteren. Bijvoorbeeld eerst alle niet-0x20 bytes, dan een reeks bytes die de genoemde 1-bits en 0-bits bevat en dan de 0x20 langte-bytes.

[Verwijderd]

@TS:

Probeer eens de opdracht van begin tot einde nogmaals te beschrijven waarbij je de verwoording van de docent los weergeeft van jouw eigen interpretatie.

Nu snapt niemand er iets van eigenlijk, waarschijnlijk jij zelf ook niet.

[.oisyn]

EddoH schreef op maandag 16 augustus 2010 @ 17:11:
[...]

Dat de opdracht op zich niet duidelijk is wil niet zeggen dat het verder ook geen duidelijke punten aanstipt.

Het doel is optimalisatie van de bestandsgrootte.

[ Voor 10% gewijzigd door .oisyn op 16-08-2010 17:16 ]