[alle talen] best strategie voor doorsturen binaire data

[hobbit_be]

Voor een project moet ik vanaf een mobieltje (series 60, python) bineare (plaatjes) doorsturen naar een server (custom NOT http). Waarom custom: HTTP heeft voor de applicatie teveel overhead (elke byte cost heel wat aan GPRS kosten met onze suppliers) en ook omdat we een continue heen en terug hebben.

dat werkt allemaal al.

Alleen zoek ik nu de meest efficiente manier om de plaatjes naar de server te sturen. Er wordt tamelijk veel 'gepraat' tussen client en server dus gebruik ik \0 (0 value) om te onderscheiden van berichten.

EN het probleem is natuurlijk dat ik de plaatjes wil doorsturen met zo min mogelijk data MAAR zonder gebruik te maken van die ene \0.

Base64, UUEncode etc lijken me overkill (ten eerste veel te groot) zeker omdat ik maar 1 value niet mag doorsturen.

Maar uurtje zoeken op Google levert geen pratische aanpak op van hoe ik die data eenvoudig kan 'escapen' zodat \0 er niet meer in voorkomt.

ie: vervang alle \0 door een code, maar wat als die code dan weer ergens voorkomt? dit dan weer opvangen door een escape token?

misschien heeft iemand een betere manier?

[Gerco]

De eenvoudigste manier is om \0 in de image data te vervangen door \0\0 en dan aan de serverkant alle instanties van \0\0 vervangen door \0. Dan stuur je dus nog wel \0 door en moet je \0\0 negeren als scheidingsteken tussen je berichten. Als dat echt geen optie is, kun je ipv \0 misschien wel \1 gebruiken:

Je vervangt dus \0 in de image data door \1 en als je een echte \1 tegenkomt, maak je daar \1\1 van. Aan de andere kant vervang je eerst alle enkele \1 door \0 en dan alle instanties van \1\1 door \1.

[ Voor 8% gewijzigd door Gerco op 11-07-2006 22:24 ]

[hobbit_be]

dus je encode deze image: 0011.2109.8033 naar

1) vervang 1 naar 11 -> 11111111.21109.8033
2) vervang 0 naar 1 -> 11111111.21119.8133

dan server:
nou ik moet die vast niet uitleggen maar der is geen manier om de eerste segment terug te decoden want kan net evengoed 00000000 zijn als 101000 of nog wat combinaties...

het is eigen net dat wat het zo moeilijk maakt en waar ik dus niet uitgeraak - ik vraag me dus gewoon af of het op telossen valt met slechts 2 replaces... (en de optie om eerste size door te geven doe ik liver niet omdat deze code ook via bluetooth moet gaan werken en daar is de zekerheid van ontvangst veel minder (en dus een terminator is vree handig)

[Verwijderd]

Misschien kan je bij het sturen van dat plaatje gewoon eerst zeggen hoeveel data hij moet verwachten?
Dus:
[\0] [data grootte van plaatje] [plaatje] ...

[edit] En als je zekerheid van ontvangst minder is, dan ben je dus ook niet zeker dat die \0 aankomt lijkt mij? In dat geval kan je sowieso best een simpele CRC check meesturen en een pakketgrootte.
Die pakketgrootte moet maar 4 byte zijn en die CRC check kan in 1 byte ofzo.

Je kan natuurlijk ook gewoon pakketjes verzamelen om ze dan samen te versturen. Het protocol dat 1 niveau lager ligt zal sowieso ook headers en checks meesturen, waardoor het handiger kan zijn dat jij al je superkleine pakketjes al even samenvoegt alvorens je verzend (je verzend dan bvb maar per x milliseconden de buffer met pakketjes).

[ Voor 67% gewijzigd door Verwijderd op 11-07-2006 22:46 ]

[Gerco]

hobbit_be schreef op dinsdag 11 juli 2006 @ 22:37:
dus je encode deze image: 0011.2109.8033 naar

Dan vervang je toch 0 door 11 en 1 door 12. Je image word dan:
11111212.212119.81133

De server kan dan gewoon teken-voor teken lezen en er weer de goede bytes van maken:

code:

11 11 12 12 . 2 12 11 9 . 8 11 3 3 = 
 0  0  1  1 . 2  1  0 9 . 8  0 3 3

Met deze oplossing zou je zelfs klaar kunnen zijn met:

code:

data = replace(data, '\1\1', '\0');
data = replace(data, '\1\2', '\1');

[ Voor 59% gewijzigd door Gerco op 11-07-2006 23:41 ]

[Erik Jan]

Om dingen te gaan escapen lijkt me een beetje omslachtig, je kan toch gewoon binaire data over je TCP connectie sturen? Als je \0 gaat vervangen door \0\0, dan wordt je plaatje in het ergste geval 2x zo groot. In een "normaal" geval raak je alsnog een aantal dozijn bytes kwijt bij een gewoon plaatje. Niet zo handig als alles zo kort mogelijk moet blijven.

Als je niet zeker bent van de integriteit van je data, hoe weet je dan of je terminator wel goed aankomt? Over het algemeen is het handiger dit over te laten aan de transport-laag, die je dus met TCP al hebt. Over bluetooth zal je dan zelf iets bovenop dit protocol moeten implementeren.

Het hangt er puur van af hoe flexibel je wil zijn. Natuurlijk moet je gaan werken met lengte-velden etc, zoals elk ander protocol. Het meest simpele is om de eerste byte van elk bericht te gebruiken om het type bericht te onderscheiden, dat geeft je al de mogelijkheid tot 256 verschillende typen. Je kan het verder doorvoeren door bijvoorbeeld een byte te reserveren die aangeeft hoe lang het komende lengte-veld is, of door bitmasks te gebruiken, zodat de eerste helft van een byte al bepaald wat de betekenis van de andere 4 bits is.

[Grijze Vos]

Kun je niet de grootte van je binary data in de eerste byte stoppen? Dan weet je gelijk wanneer je binary data stopt.

(Hmz, over laatste alinea van Erik Jan heengelezen..)

[ Voor 20% gewijzigd door Grijze Vos op 12-07-2006 01:38 ]

[hobbit_be]

Gerco schreef op dinsdag 11 juli 2006 @ 23:36:
Met deze oplossing zou je zelfs klaar kunnen zijn met:

code:

data = replace(data, '\1\1', '\0');
data = replace(data, '\1\2', '\1');

idd, tis dan gewoon de decoding die niet via een replace kan gaan (ie parse two, if special, else go first etc... ). Er zal vast geen manier zijn om een dubble replace aan beide kanten te doen (een simpele replace, vast wel een RE die het doet)

Het punt dat het wel aankomt is idd waar, MAAR het is een beetje als een MPEG stream: hoewel er veel data missende kan zijn zal het nooit een terminator aankrijgen (ie hence het UNIQUE van de \0).

dwz

Het kan heel de tijd mislopen maar als die dan een \0 opnieuw tegenkomt weet ie tenminste waar te herstarten.Die length en special packages zijn als de communicatie eenmaal 'kaput' is ook niet meer recoverable.

Ik nam aan dat dit een van de redenen was waarom zoveel 'oude' protocollen met zo'n terminators werken...

Nu goed die replace gaat is idd meer data opleveren dan geplanned en ik zal dus zien hoe reliable het allemaal is met size based messages...

offtopic:
PS een van de vragen die ik steeds heb is wat als je CRC code verkeerd doorkomt

[Tyf]

Wat jij wilt doen is al opgelost op de datalink laag van het osi model, als je daar even opzoekt kun je makkelijk een goeie oplossing vinden. Een methode die ik zou gebruiken is start- en eindvlaggen met bit-stuffing. Bij osi werken ze met frames, in jou geval vervang je dit door het prentje. Met dit heb je al je probleem opgelost om aan te geven waar je prentje begint en waar hij eindigt. Wat je wel nog niet oplost is datacoruptie, dit moet opgevangen worden door crc check. Nu kan je een prentje beginnen zenden zonder dat er geweten is hoe groot hij is.

• Je begint en eindigt het zenden van je prentje door een header (vlagbyte) te sturen onder de vorm van 01111110 bits (de vlagbyte), hierdoor weet de onvanger ik ga nu een prentje ontvangen.
• Dan zend men de data van het prentje MAAR in deze data moet men na elke opeenvolging van van 11111 (5 maal) een extra nul toevoegen.
• Bij de ontvanger gaat men bij elke opeenvolging van 5 1 bits (11111) gevolgd door een nul, de nul laten vallen. Hierdoor heb je weer je originele data, plus aanduiding van header en tail.

Je enige extra kosten zijn, de header/tail en voor elke 11111 een extra 0.

Echt alles wat je wilt doen is al in geuren kleuren bedacht en uitgewerkt hoor. Inclusief al je problemen. Je wilt het wiel opnieuw uitvinden. Lees wat over de datalink laag in het osi model.

[ Voor 4% gewijzigd door Tyf op 12-07-2006 11:52 ]

[hobbit_be]

Hey tyf thanks voor die tip, al die uitdrukkingen zijn perfecte plekken voor me voor te googlen,

Ik was er ook niet op uit om iets uit te vinden hoor : gewoon handige manieren vinden die al bestaan + concepten - het is gewoon niet evident om de termen te vinden. (nooit IT gestudeerd dus ontbreek heel wat theoretische kennis).

Jullie zijn allemaal bedankt voor jullie hulp. Hopelijk kan ik iemand ooit terug helpen met python op series 60

[Tyf]

Hehe ja het is idd lastig te zoeken op termen als je de termen niet kent.
Maar je netwerkkaart op de pc werkt op de manier die ik beschreven heb dus het werkt wel

misschien nog een voorbeeldje

A ) 011011111111111111110010 te zenden data
B ) 011011111011111011111010010 hoe het verzonden wordt
C ) = A na omzetting bij ontvangst

Als je zoekt, goed opletten je hebt Byte stuffing en bit stuffing. Het is de bit stuffing die je wilt hebben, bij byte stuffing zit je vast aan tekens van 8 bits (vandaar de byte in byte stuffing )

[BestTested!]

Tyf schreef op woensdag 12 juli 2006 @ 11:58:
Hehe ja het is idd lastig te zoeken op termen als je de termen niet kent.
Maar je netwerkkaart op de pc werkt op de manier die ik beschreven heb dus het werkt wel

misschien nog een voorbeeldje

A ) 011011111111111111110010 te zenden data
B ) 011011111011111011111010010 hoe het verzonden wordt
C ) = A na omzetting bij ontvangst

Als je zoekt, goed opletten je hebt Byte stuffing en bit stuffing. Het is de bit stuffing die je wilt hebben, bij byte stuffing zit je vast aan tekens van 8 bits (vandaar de byte in byte stuffing )

Tanenbaum beschrijft dit erg goed (naar mijn mening) in Andrew S. Tanenbaum (2003) "Computer Networks". Misschien dat je dit ergens kan vinden/lenen.
Heb 't zelf gebruikt tijdens mijn studie...
http://www.fdaw.unimaas.n...0en%20Telematica/TET3.ppt

[Soultaker]

De suggestie van Tyf is knap waardeloos; een overdreven ingewikkelde vorm van escaping. (Op link level is het wel nuttig, maar dat is dit dus niet!)

Inhoudelijk: een makkelijke en redelijk efficiente strategie is simpelweg het doorsturen van de grootte vóórdat je begint te zenden, zoals Vich al suggereerde. Als je de overhead van hele kleine packets wil beperken kun je iets doen als één byte gebruiken om de grootte te coderen, en opvolgende packets samenvoegen totdat de grootte onder de 255 komt.

Drie packets van 300, 200 en 255 bytes worden dan zo verstuurd:
255, [255 bytes data], 45, [45 bytes data], 200, [200 bytes data], 255, [255 bytes data], 0.

Tenslotte kun je overwegen iets als Huffman-codering toe te passen; je kunt dan makkelijk een terminator aan het het alfabet toevoegen, zodat je een alfabet met 257 symbolen codeert - eigenlijk hetzelfde wat er gebeurt met die bitstuffing. Dat is eigenlijk alleen zinnig als de data die je gaat verzenden zelf niet gecomprimeerd is; anders is de hierboven beschreven manier gewoon praktischer.

[ Voor 3% gewijzigd door Soultaker op 12-07-2006 16:19 ]

[Tyf]

Als je osi model zou lezen zie je dat uw oplossing daar ook in staat soultaker, met als grote MAAR dat datacoruptie totaaal niet mag voorkomen. Als je door datacoruptie de bits verliest of veranderd die de grote van het prentje aangeven, weet de ontvanger totaal niet meer wat te doen en blijft hij eindeloos of telang/te kort denken dat het prentje aan het binnen komen is. Uw oplossing is wat men ooit eerst aan gedacht heeft, tot men het grote nadeel ervan vond. Namelijk uw lijn waarover je zend isniet perfect en je verliest gegarandeerd gegevens (zeker draadloos).

@BestTested! awel daar komt het ook uit het voorbeeldje, heb het boek hier liggen.

[ Voor 18% gewijzigd door Tyf op 12-07-2006 18:13 ]

[Grijze Vos]

Tyf schreef op woensdag 12 juli 2006 @ 18:10:
Als je osi model zou lezen zie je dat uw oplossing daar ook in staat soultaker, met als grote MAAR dat datacoruptie totaaal niet mag voorkomen. Als je door datacoruptie de bits verliest of veranderd die de grote van het prentje aangeven, weet de ontvanger totaal niet meer wat te doen en blijft hij eindeloos of telang/te kort denken dat het prentje aan het binnen komen is. Uw oplossing is wat men ooit eerst aan gedacht heeft, tot men het grote nadeel ervan vond. Namelijk uw lijn waarover je zend isniet perfect en je verliest gegarandeerd gegevens (zeker draadloos).

@BestTested! awel daar komt het ook uit het voorbeeldje, heb het boek hier liggen.

Ik denk dat dat mobieltje een protocol gebruikt voor data-overdracht dat zal zorgen voor de aankomst van de packages? Net zoals TCP dat doet. (Misschien is het zelfs wel TCP over wireless.)

[Tyf]

ja in dat geval is de bitstuffing methode wat overkill, ging ervanuit dat het echt allemaal zelf geregld moest worden. nu ts zal wel zien wat em wilt

[Verwijderd]

Kun je niet gewoon met een soort vaste headers werken in je binaire data en dit versturen over TCP/IP? Iets als:

char[4] - versie
char[80] - name
dword - data length, len
bytes[len] - image data

Dan omzeil je de problemen met die terminator en het biedt meer flexibiliteit. Gewoon een idee, kan natuurlijk zijn dat ik het probleem verkeerd begrepen heb

[Soultaker]

Tyf schreef op woensdag 12 juli 2006 @ 18:10:
Als je osi model zou lezen zie je dat uw oplossing daar ook in staat soultaker, met als grote MAAR dat datacoruptie totaaal niet mag voorkomen. [..] Namelijk uw lijn waarover je zend isniet perfect en je verliest gegarandeerd gegevens (zeker draadloos).

Maar met GPRS heb je al foutdetectie, en op IP nivo ook nog eens. De TS is er niet zo specifiek over, maar ik vermoed dat hij niet bezig is met de implementatie van een protocol op link level -- alleen dáárvoor zijn de technieken die je noemt zinnig. Op een hoger nivo (zoals GPRS packets of IP) is het gewoon zinloos.

Als je door datacoruptie de bits verliest of veranderd die de grote van het prentje aangeven, weet de ontvanger totaal niet meer wat te doen en blijft hij eindeloos of telang/te kort denken dat het prentje aan het binnen komen is. Uw oplossing is wat men ooit eerst aan gedacht heeft, tot men het grote nadeel ervan vond.

Met bit stuffing heb je precies dat zelfde probleem (wat als het terminatorsignaal gestoord wordt?). Die codering met terminators is dus om packets te scheiden en garandeert op zichzelf niet de afwezigheid van fouten, óók niet in de transmissie van terminators!

Daarnaast is bit stuffing op sommige media nuttig, omdat series van gelijke bits met sommige technieken meer fouten opleveren dan afwisselende bits, waardoor het nuttig is om wat losse nullen tussendoor te gooien af en toe. Het sturen van een terminator na én voor een packet is ook ten behoeve van redundantie; zo wordt het packet gescheiden van een voorgaande packet die niet geheel ontvangen is.

Maar dit is allemaal irrelevant als de TS al met TCP/IP werkt.

[ Voor 6% gewijzigd door Soultaker op 12-07-2006 19:48 ]

[hobbit_be]

de TS ( ) is idd niet direct bezig op link level. Voor een deel gaat het via GPRS , en de bluetooth via , nou ja bluetooth (met serial connection). Vooral die laatste is nogal prone om het te laten afweten (afstand gedoe etc). Maar in de bluetooth geval is size niet zo'n issue. Daarvan is transmissie immers free.

Ondertussen heb ik al een werkende code , door , en nu gaan jullie me afschieten, via die 2 replaces. met dus de \0 terminator.

De reden dat ik die OSI layer moest laten vallen was dat alles op BIT niveau gebeurt en dat via Python op de mobiel veel te veel resources zou impalmen. (Die huffman encoding moet ik nu wel eens gaan zien).

De code nu is zoals gezien die Tyf, met 2 replaces aan encoder en decoder vlak en dit is quasi instanteneous. (duidelijk betere str replace in python dan java ).

Door het gebruik van de \0 kan ik ook super snel de messages parsen (ie van elkaar) allemaal op string niveau. wat erweer voor zorgt dat ik geen for loop heb op python scale (wel in de gebruikte find natuurlijk). En veel belangrijker voor fast development cycles: alle messages kunnen eender wat zijn + leesbaar: ie niet zo'n nood voor perfecte ontleding van bits en bytes maar string.splits.

Aangezien per type van message er veel verschillende argumenten (variablen) kunnen worden doorgegevn maakt dit alles zoveel simpeler voor te debuggen

En daardoor was alles klaar in een uurtje (aanpassen server en mobiele code).

Omdat ik toch bezorgd was door size changes heb ik der een paar doorgestuurt (images die in de applicatie neem) en de overhead is zo rond de 3%. Er is meer verschil in de JPG encodering dan in de overhead + eenvoudig te coden + flash socket compatible (wat wil zeggen dat ik de code kan herbruiken en ook rechtstreeks via flash (en flash lite 2 dito) can communiceren) + recoverable on top.

Wat niet wil zeggen dat ik wel hoop een combo te gebruiken... \0 voor terminator maar idd ook een size doorgeven. ie: de size is de grote tussen opeenvolgende \0 die echt iets willen zeggen. Zo kan die ook recoveren.

Op mijn werk moet alles snel, stabiel en direct marcheren dus vaak geen tijd voor 'perfect' solutions waar , naar jullie passie in de replies wel naar streven.

Nogmaal bedankt..

[Hydra]

hobbit_be schreef op woensdag 12 juli 2006 @ 22:56:
Wat niet wil zeggen dat ik wel hoop een combo te gebruiken... \0 voor terminator maar idd ook een size doorgeven. ie: de size is de grote tussen opeenvolgende \0 die echt iets willen zeggen. Zo kan die ook recoveren.

Compleet pointless. Op het niveau waar jij werkt zorgt TCP/IP al voor de foutcorrectie. Je had het over een overhead van 3% zei je? Als je gewoon vooraf een paar bytes (2 of 4 als de plaatjes groter zijn dan 64k) heb je max 4 bytes per plaatje overhead. Da's helemaal niks.

[hobbit_be]

ik begrijp je frustratie,

maar zoals ik probeerde uit te leggen in mijn laatste post was dat voor bepaalde zaken flexibiliteit + easy of code and adaptability belangrijker dan de gemiste bytes.

ik hoopte alleen dat er een methode was met minder overhead (op byte , niet bit niveau) + die WEL die terminator heeft.

ie: tis een beetje zoals vragen: ik zoek de snelste manier om met de auto van amsterdam naar moskou te rijden. en het antwoord is: neem het vliegtuig want dat is sneller. Das juist maar het is niet het antwoord op de vraag ...

Heb wel veel bijgeleerd dat als ik eenmaal in TCP/IP zit ik me een worst moet aantrekken van correctie en CRC... (waarom dat er op newsgroups nog die PAR bijzitten? )

[Hydra]

hobbit_be schreef op donderdag 13 juli 2006 @ 16:25:
ik begrijp je frustratie,

Frustratie?

maar zoals ik probeerde uit te leggen in mijn laatste post was dat voor bepaalde zaken flexibiliteit + easy of code and adaptability belangrijker dan de gemiste bytes.

Ik zie niet hoe jouw oplossing makkelijker en flexibeler is dan gewoon het aantal bytes te prefixen. Daarnaast heb je problemen met overhead (jouw oplossing heeft waarschijnlijk meer overhead dan gewoon HTTP). Maargoed, het is jouw feestje.