[C#] Jak na konečný automat

[PiranhaGreg]

Ahoj, potřebuji získávat nějaká data z dost velkého binárního souboru. Problém je, že od něho nemám dokumentaci. Nechce se mi ale týden (ne-li víc) luštit jak je strukturovaný, když pak stejně potřebuju jen zlomek dat, které vím jak hledat.

Zároveň bych ale ty správný data potřeboval najít max v lineárním čase vzhledem k velikosti souboru. Napadlo mě tedy pořešit to přes (něco jako) konečný automat. Moje bezhlavá implementace je ale jaksi hodně dlouhá a celkově to tak nemůžu nechat. Navíc tam detekuju jen jednu ze čtyř sekvencí. Počítám, že když bych do toho tímto stylem chtěl přidat i ty zbývající, tak se upíšu.

Takže jak na to znovu a správně? Nemusí to být nutně přes ten konečný automat, pokud vás napadne něco jinýho. Ale vstupem by měl být stále stream. Nahrávání celýho souboru do pole bytů bych se chtěl vyhnout. Jen pro představu, už tahle funkce mi tam najde 46 576 záznamů, kde průměrný název proměnný má 18 znaků a její obsah 174. Těch dalších typů záznamů bude ještě víc.

[pucmeloudek]

hledas nakej prefix nebo co? zkus to pro zacatek bez goto... a pak trochu slovne popsat, o co jde, se mi to nechce zpetne lustit z kodu.

[darm]

Co to je za typ dat? Na dolování něčeho podle regexpu bohatě stačí třeba grep.

[gandor]

V principe ides spravne. Len ten kod je prasacky a budes mat problem ked budes vytahovat viac veci.
Stavovy automat bude vzdy viac kodu a to je v pohode, ale preco nemozu byt jeho jednotlive stavy triedy obsahujuce prechody a podobne? Definujem X tried (kazda pre jeden stav), ktora bude obsahovat svoju condition a aj svoje prechody (a akcie). Na zaklade toho mi vznikne pekny priehladny graf, ktory budes vediet relativne lahko extendovat.
Idealne je, aby dedili s jednej triedy, ktora bude definovat nejake pomocne veci (read byte zo streamu a podobne).

Regexp v binarnom subore nebude nejak velmi pouzitelny. Ale pokial su tahane data dostatocne strukturovane, tak by to mohlo zjednodusit vec. Urcite ale nie grep ktory vytahuje cely riadok (co je riadok v binarnom subore?) ale skvor nejaky "tradicny" regexp z "normalnych" jazykov....

[Nargon]

Tak jsem luštil ten tvůj kód. Z toho co jsem vysledoval, tak by to mělo odchytávat takovýto kód:

Kód: Vybrat vše

0x01 0x00 0x00 0x00 NazevPromene 0x0a 0x00 0x00 0x00 0x00 0x01 0x30 0x41 0x00 4ByteData1 4ByteData2 4ByteData3 4ByteData4 TextData 0x0a

S tím že "NazevPromene" a "TextData" jsou variabilní a předem neznámé délky.
Pak "NazevPromene" musí obsahovat jen znaky A-Z, a-z, 0-9, a podtržítko _, cokoliv jiného není povolené.
Data1 až Data4 jsou vždy o délce 4Byty.

Je to tak správně a je to vše? To abych nevymýšlel něco podle špatného zadání. Určitě se to dá nějakým způsobem optimalizovat. Ale než se nad tím zamyslím tak chci vědět že nebudu věnovat čas něčemu špatnému.

[PiranhaGreg]

Tak jsem luštil ten tvůj kód. Z toho co jsem vysledoval, tak by to mělo odchytávat takovýto kód:

Kód: Vybrat vše

0x01 0x00 0x00 0x00 NazevPromene 0x0a 0x00 0x00 0x00 0x00 0x01 0x30 0x41 0x00 4ByteData1 4ByteData2 4ByteData3 4ByteData4 TextData 0x0a

S tím že "NazevPromene" a "TextData" jsou variabilní a předem neznámé délky.
Pak "NazevPromene" musí obsahovat jen znaky A-Z, a-z, 0-9, a podtržítko _, cokoliv jiného není povolené.
Data1 až Data4 jsou vždy o délce 4Byty.

Je to tak správně a je to vše? To abych nevymýšlel něco podle špatného zadání. Určitě se to dá nějakým způsobem optimalizovat. Ale než se nad tím zamyslím tak chci vědět že nebudu věnovat čas něčemu špatnému.

Jop, vysledoval jsi to správně (+ první znak u proměnné nesmí být číslo). Když to trochu rozvedu...

Počáteční sekvence 0x01 0x00 0x00 0x00 je vždycky před NazevPromenne, ale nemusí nutně značit, že tam ta proměnná bude. Jsou tam i nějaký jiný data, kde se tyhle sekvence také objevují. Proto hned tak přísně validuji, že se jedná o proměnnou, abych případně mohl zahlásit false positive a jet od začátku.

Dále název proměnné i případný text vždy končí tím 0x0a. Text může být v podstatě cokoliv, ale bývá tam hlavně windows-1250 a windows-1251.

Ta následující sekvence 4x 0x00 tam bohužel není vždy. Ještě jsou tam pro jiný typy (viz dále) tvary 0x02 0x00 0x00 0x00 a 0x07 0x00 0x00 0x00 (a možná ještě něco). I v tomhle místě je ale ještě potřeba detekovat počáteční sekvenci 0x01 0x00 ..., protože pořád není jistota, že jde o správný data .

No a pak je tam konečně sekvence, která určuje typ proměnné. Tři nejdůležitější jsou tyto

0x01 0x20 0x40 0x00 = var int
0x01 0x20 0x41 0x00 = const int
0x01 0x30 0x41 0x00 = const string

ale časem tam chci mít ještě podporu pro float, RGB barvu a několik dalších, takže bych minimálně tuhle část potřeboval nějakou rozšiřitelnou.

Pak jsou tam různý custom hodnoty podle typu, ale to už je v pohodě, protože vím na čem jsem. Sekvence pak vždy končí čtveřicí 0xff 0xff 0xff 0xff.

Jinak chci ty data vracet průběžně jak to mám teď. Budu s tím dělat ještě nějaký čachry pomocí LINQ a ani je třeba nebudu potřebovat načíst všechny. V předpisu metody bude jako návratová hodnota nějaký předek či interface.

Ale spíš než funkční implementace mi stačí nějaké typy jak na to v úhlednějším stylu, ale abych zároveň zachoval rychlost, která je tu důležitá.

Regexp v binarnom subore nebude nejak velmi pouzitelny. Ale pokial su tahane data dostatocne strukturovane, tak by to mohlo zjednodusit vec. Urcite ale nie grep ktory vytahuje cely riadok (co je riadok v binarnom subore?) ale skvor nejaky "tradicny" regexp z "normalnych" jazykov....

No když jsem se těmi daty prokousával, tak jsem si na to nějaký Regex napsal. Např. na tu sekvenci, kterou hledám v mé prvotní implementaci funguje v Sublime Text docela dobře

Kód: Vybrat vše

(?s)\x01\x00\x00\x00([ -˙]*?)\x0a\x00{4}\x010A\x00(.{4}).{4}\x01\x00\x00\x00.{8}([ -˙]*?)\x0a˙˙˙˙

+ bych tam ještě musel dopsat nějaký validace. Min. v Sublime Text je to ale hodně pomalý, asi hodně hodně hodně těžko bych do toho regexu narval všechny ty hledaný sekvence a pak taky C# pracuje s UNICODE a nevím nevím, jak by se mu líbily ty binární data, který bych mu podstrčil jako string. Navíc bych to nejspíš zase musel celý nahrát do paměti.

Jinak jak jsi to myslel s těmi třídami a stavy? Co jsem si kreslil na papír cca stavovej automat, kterej odpovídá celýmu řešení, tak je tam těch stavů opravdu hodně. Na to asi tolik tříd definovat nebudu .

[Nargon]

Hmm, tak po vyzkoušení to odchytává trochu jiná data.

Kód: Vybrat vše

0x01 0x00 0x00 0x00 NazevPromene 0x0a 0x00 0x00 0x00 0x00 0x01 0x30 0x41 0x00 4ByteData1 4ByteData2 4ByteTrash 4ByteData3 4ByteData4 TextData 0x0a

Je tam navíc 4ByteTrash, holt 20 != 4*4 ale je to 20 = 5*4

Já jsem něco zkusil vyplodit, a kompletní kód máš tady: http://paste.ofcode.org/cW5iaUzFa2q4dwXhHSxSpn
a tu hlavní část dám i sem

Kód: Vybrat vše

    class StreamParser
    {
        int lastByte = -1;
        private ulong lastRead = ulong.MaxValue;
        private ulong last2Read = ulong.MaxValue;
        Stream s;

        Encoding windows1250 = Encoding.GetEncoding(1250);
     
        public StreamParser(Stream input)
        {
            s = input;
        }

        int ReadByte()
        {
            lastByte = s.ReadByte();
            last2Read = (last2Read << 8) | (lastRead >> 56); //bitová magie, vždy se o 1B posune a načte se další hodnota
            lastRead = (lastRead << 8) | (ulong)lastByte; //zpětně si pamatuje 16B dat, což stačí na identifikaci správné pozice
            return lastByte;
        }       

        Queue<byte> variable = null;
        string varName = null;
       
        public IEnumerable<VariableEntry> ReadData()
        {
            while (ReadByte() != -1)
            {
                if ((lastRead & 0xFFFFFFFF) == 0x01000000ul) variable = new Queue<byte>();

                if (variable != null)
                {
                    if (lastByte == 0x0a) { varName = windows1250.GetString(variable.ToArray()); variable = null; }
                    else variable.Enqueue((byte)lastByte);
                    continue;
                }

                if ((last2Read & 0xFF) == 0x0a)
                {
                    switch (lastRead)
                    {
                        case 0x0000000001204000ul:
                        case 0x0200000001204000ul:
                        case 0x0700000001204000ul: //spravna data var int                         

                        case 0x0000000001204100ul:
                        case 0x0200000001204100ul:
                        case 0x0700000001204100ul: //spravna data const int                         

                        case 0x0000000001304100ul:
                        case 0x0200000001304100ul:
                        case 0x0700000001304100ul: //spravna data const string
                            {
                                byte[] bytes = new byte[20];
                                s.Read(bytes, 0, 20);
                                Queue<byte> content = new Queue<byte>();
                                while (ReadByte() != -1)
                                {
                                    if (lastByte == 0x0a)
                                    {
                                        yield return new VariableEntry()
                                        {
                                            Name = varName,
                                            Content = windows1250.GetString(content.ToArray()),
                                            Type = BitConverter.ToInt32(bytes, 0),
                                            Valuel1 = BitConverter.ToInt32(bytes, 4),
                                            Valuel2 = BitConverter.ToInt32(bytes, 12),
                                            Valuel3 = BitConverter.ToInt32(bytes, 16),
                                        };
                                        break;
                                    }
                                    else content.Enqueue((byte)lastByte);
                                }
                                break;
                            }
                    }
                }
            }
            yield break;
        }
    }

Já jsem nepoužil stavový automat, ale šel jsem na to trochu jinak. Při načítání si tvořím malý buffer o velikosti 8+8B, který posouvám a je v něm zpětně uložených 16B dat, které stačí na identifikaci sekvence 0x0a 0x00 0x00 0x00 0x00 0x01 0x30 0x41 0x00. Navíc to není problém rozšířit, jen do switche přidat další sekvenci. Ikdyž tam už jsem ti zadal všechny možnosti co jsi tu napsal.
Není tam ta kontrola na název proměnné, aby to obsahovalo jen ty validní znaky a ani ten konec na 0xff 0xff 0xff 0xff, ale snad to není nutné. Ikdyž to tam půjde doplnit.

Jen tak ze zvědavosti. Můžeš vyzkoušet rychlost na tom tvém souboru v porovnání s tvým řešením? Celkem mě to zajímá. Lineární složitost tam stále je, ale neodhadnu zda ty binární operace jsou rychlejší než skoky mezi stavy nebo naopak.

[xmisak]

Já to napsal v Céčku takto:
Skoro bych se vsadil, že efektivněji to napsat nejde Troufl by si někdo napsat kód (v libovolném jím zvoleném jazyce), který poběží na stejném hardware v rychlejším čase?

Kód: Vybrat vše

#include <stdio.h>

#define BLOK 8192
#define MAX_SEARCH 100

char buf[BLOK+MAX_SEARCH];

int shoda(char *a,char *b,int n)
  {
  int i;
  for (i=0;i<n;i++)
    if (a[i]!=b[i]) return(0);
  return(1);
  }
 
int hledej(char *fn,char *co,int n)
  {
  FILE *f;
  int i,nacteno,zac,l=0;
 
  f=fopen(fn,"rb");
  zac=MAX_SEARCH;
  do {
    nacteno=fread(buf+MAX_SEARCH,1,BLOK,f);
   for (i=zac;i<nacteno;i++)
     if (shoda(buf+i,co,n)) return(l+i-MAX_SEARCH);
   for (i=0;i<MAX_SEARCH;i++) buf[i]=buf[i+BLOK];
   zac=1;
   l+=BLOK;
    } while (nacteno==BLOK);
  fclose(f);
  return(-1);
  }

int main()
  {
  char co[4]={'a','h','o','j'};
  printf("%d\n",hledej("data.txt",co,4));
  }

-- 30. 9. 2015 09:08 --

V gigabajtovém souboru s hledaným 9-bajtovým binárním řetězcem na konci mi hledání trvá 4,47 sekundy. Pravda, mám SSD disk.

[pucmeloudek]

mno, resit primitivni algoritmus, kterej stejne vzdycky bude brzdit medium, ze kteryho se cte... ze vas to bavi

trocha literatury na algoritmy hledani substringu (kdyby to nebrzdil onen disk, jinak je to o houne)

http://www-igm.univ-mlv.fr/~lecroq/string/index.html

btw. v tom Ccku je na prvni pohled brutalne neoptimalni tohle:

for (i=0;i<MAX_SEARCH;i++) buf[i]=buf[i+BLOK]

kopirovat buffer fixni velikosti po jednotlivych byte, fuj...

[xmisak]

No já zde kopíruji 100 bajtů na každých 8192. I kdyby se tahle část použitím funkce přepsané do assembleru (která ve finále stejně dělá to samé) zrychlila třeba na polovinu, nebo na třetinu, na výsledný běh to bude mít zcela zanedbatelný vliv.

Ostatně, teď jsem to zkusil. Ten řádek jsem nahradil
memcpy(buf,buf+BLOK,MAX_SEARCH);
a čas zůstal s přesností na setinu sekundy stejný...

Jinak zcela souhlasím s tím, že celý ten problém je naprosto banální a triviální

[pucmeloudek]

no mne slo jenom o to poukazat na to, jak zvraceny je psat vlastni tezce neoptimalni algoritmy, kdyz mam knihovni volani...

aneb zkratka byla sice delsi, ale zato horsi cesta

btw. ta nejsnazsi optimalizace celyho algoritmu je pouzit strchr na hledani mist, kde vubec ma smysl se zacit zabyvat nakym cyklem pres hledany retezec...

[gandor]

xmisak: Nedavaj taketo vyzvi, lebo ked sa vezmu mikrooptimalizacie do uvahy, tak ten kod je vyslovene pomaly Samozrejme suhlasim s pucmeloudek a zameral by som sa na ine veci ako percenticka vykonu...

Pucmeloudek: K tym triedam - kazda by mala predstavovat urcity stav v ktorom som - citam cisla, citam text ktory je na konci niecim ohraniceny, atd atd. Tento postup nieje vykonnostne ani zdaleka najoptimalnejsi. Ale je optimalny z hladiska toho, ze lustim nieco a neviem co a neviem co sa s toho neskvor vykluje a potrebujem sa vediet rychlo zorientovat v kode a doplnit do neho lubovolne features.
Samozrejme nerobis novu triedu pre kazdu premennu - len pre kazdy "stav" (teraz citam premenna1 premenna2 premenna3 premenna4) vramci daneho streamu. V takom pripade vies pre kazdu cast si precitat len tolko dat, kolko potrebujes vtedy ked potrebujes.

Ale kedze si sa vybral uz Nargonovym riesenim, tak by som sa ho drzal - koniec koncov urcite pojde rychlejsie a da sa aj doplnat...

[xmisak]

gandor: Vysloveně pomalý kód? Uff, tak sem s konkrétními čísly! Napiš svoji verzi a na jednom stroji pak pusť tu moji a tu svoji, a pochlub se srovnáním
pak můžeme posoudit, co je "vysloveně pomalé" a ne-"vysloveně pomalé"
Keckat od stolu je tak snadné...

[xmisak]

pucmeloudek: strchr přece hledá v null-terminated řetězci. Takže když budou vstupní data obsahovat nulu, hledání tam skončí. To je nám na nic. I bez ohledu na to bych se navíc vsadil, že tímhle vylepšením v reálu nezískáš prakticky nic.

Jinak, já bych ty vestavěné funkce až tak nepřeceňoval. Jak říkám: zkuste ty své moudré úvahy implementovat, a hned budeme vidět.

[pucmeloudek]

no tak memchr, bozinku, jde o princip.
to, ze tezko neco clovek muze ziskat (protoze to visi na pomalym ctenim disku, todiz je to cela diskuze o houne), rikam od zacatku.