Forum » Programiranje » Generiranje CRC-ja
Generiranje CRC-ja
kriko1 ::
Imam bolj matematični problem kot pa programerski.
Vem da java ima CRC-16 ter CRC-32 generatorje, vendar bi spisal svojega ker generatorski polinom se bo spreminjal
po želji (input).
Torej pri predmetu Računalniška Omrežja smo računali podobne naloge samo nad golimi biti in mi ni preveč
jasno kako bi to delal v desetiškem zapisu.
Delali pa smo tako da smo dobili podane podatke (data), polinomski generator in nato smo izračunali CRC.
Če so podatki dolžine m-bitov ter polinomski generator r-bitov + 1, je iz tega sledilo da bo končni CRC dolg r-bitov.
Nato smo nad podatki skupaj z r-biti (katere smo postavili na 0) delali XOR operacije z generatorskim polinomom in
na koncu dobili ostanek - to je bil naš CRC.
Videl sem že nekaj rešitev katere nosijo neko predefinirano tabelo (kaj v zvezi z polinomom?!):
http://www.cs.princeton.edu/introcs/51d...
- najprej me zanima kaj je tista tabela in kako se jo dobi
Naprej bom postopoma spraševal, ker upam da mi bo po temle odgovoru preostalo postalo jasno (upam).
lp
Vem da java ima CRC-16 ter CRC-32 generatorje, vendar bi spisal svojega ker generatorski polinom se bo spreminjal
po želji (input).
Torej pri predmetu Računalniška Omrežja smo računali podobne naloge samo nad golimi biti in mi ni preveč
jasno kako bi to delal v desetiškem zapisu.
Delali pa smo tako da smo dobili podane podatke (data), polinomski generator in nato smo izračunali CRC.
Če so podatki dolžine m-bitov ter polinomski generator r-bitov + 1, je iz tega sledilo da bo končni CRC dolg r-bitov.
Nato smo nad podatki skupaj z r-biti (katere smo postavili na 0) delali XOR operacije z generatorskim polinomom in
na koncu dobili ostanek - to je bil naš CRC.
Videl sem že nekaj rešitev katere nosijo neko predefinirano tabelo (kaj v zvezi z polinomom?!):
http://www.cs.princeton.edu/introcs/51d...
for (byte b : bytes) {
crc = (crc >>> 8) ^ table[(crc ^ b) & 0xff];
}- najprej me zanima kaj je tista tabela in kako se jo dobi
Naprej bom postopoma spraševal, ker upam da mi bo po temle odgovoru preostalo postalo jasno (upam).
lp
_Dormage_ ::
Kar se tiče tabele nevem točno.
Jst sem CRC implementiral tako
Vse sem delal z tipi String ker v int oz. long nisem mogu spravit dovolj velikih stevil za moje potrebe.
Od vhodne spremenljivke (data) tipa String sem jemal substringe dolzine generatorja
in izvajal XOR z generatorjem nad posameznimi znaki (char).
Seveda je se dosti šminke in fixov ker neznam lepo kodirat.
Potem je se dodatnih par vrstic, ki skribi, da ce je vmesni rezultat pri XOR-u naprimer 000110101101
Potem odstranjuje nule z desne proti levi dolker ne naleti na enico. (110101101)
In potem seveda nafila mankajoce bite z biti iz vhoda(data) dokler ne doseze dolzine CRC polinoma
(110101101000)
Dinamične spremenljivke so seveda data pa generatorski polinom, ki jih lahko poljubno spreminjaš.
Pomoje je najbolse vse skupaj rekurzivno rešit, sicer pa sem jst uporabil malo morje for zank :)
Lp
Jst sem CRC implementiral tako
Vse sem delal z tipi String ker v int oz. long nisem mogu spravit dovolj velikih stevil za moje potrebe.
Od vhodne spremenljivke (data) tipa String sem jemal substringe dolzine generatorja
in izvajal XOR z generatorjem nad posameznimi znaki (char).
Seveda je se dosti šminke in fixov ker neznam lepo kodirat.
Potem je se dodatnih par vrstic, ki skribi, da ce je vmesni rezultat pri XOR-u naprimer 000110101101
Potem odstranjuje nule z desne proti levi dolker ne naleti na enico. (110101101)
In potem seveda nafila mankajoce bite z biti iz vhoda(data) dokler ne doseze dolzine CRC polinoma
(110101101000)
Dinamične spremenljivke so seveda data pa generatorski polinom, ki jih lahko poljubno spreminjaš.
Pomoje je najbolse vse skupaj rekurzivno rešit, sicer pa sem jst uporabil malo morje for zank :)
Lp
kriko1 ::
Aja, sem že rešil :D
Polinom preračunam na začetku, potem pa se pomikam proti desni za dolžino polinoma (seveda upoštevam vmesne ostanke),
dokler ne naletim na max. dolžino niza podatka + polinoma. Xor operacije pa delam nad več biti naenkrat.
Tista tabela pa so (kot se mi dozdeva) vsi možni ostanki deljenja pri določenem polinomu, v mojem primeru ko je polinom stvar
vnosa je to brezpredmetno, saj bi se izvajanje programa krepko podaljšalo.
Polinom preračunam na začetku, potem pa se pomikam proti desni za dolžino polinoma (seveda upoštevam vmesne ostanke),
dokler ne naletim na max. dolžino niza podatka + polinoma. Xor operacije pa delam nad več biti naenkrat.
Tista tabela pa so (kot se mi dozdeva) vsi možni ostanki deljenja pri določenem polinomu, v mojem primeru ko je polinom stvar
vnosa je to brezpredmetno, saj bi se izvajanje programa krepko podaljšalo.
_Dormage_ ::
V katerem jeziku pa si pisal?
Če ni odveč (glede avtorskih pravi pa take zadeve)
Bi lahko delil tvojo kodo?
Lp
Če ni odveč (glede avtorskih pravi pa take zadeve)
Bi lahko delil tvojo kodo?
Lp
kriko1 ::
Java. Imaš slučajno za domačo nalogo? :P
(kodo lahko delim, toda če imaš za DN oddat kot jaz, potem se je potrebno zmenit za posebno plačilo :P )
(kodo lahko delim, toda če imaš za DN oddat kot jaz, potem se je potrebno zmenit za posebno plačilo :P )
Zgodovina sprememb…
- spremenil: kriko1 ()
_Dormage_ ::
Poštenost je vrlina !
Imam za domačo nalogo in za kodo ne ne bom plačal.
Bi pa cenil če lahko z tvojo pomočjo napišem svoj program :)
Hvala!
Lp
Imam za domačo nalogo in za kodo ne ne bom plačal.
Bi pa cenil če lahko z tvojo pomočjo napišem svoj program :)
Hvala!
Lp
Brane2 ::
CRC maš narejen v Linuxovem kernelu.
Poglej source. Čeprav ga bo direkt skopirat mogoče težko in predvsem sumljivo, a čisto tako za vpogled, kako je to v praksi narejeno, da dela s solidno hitrostjo mogoče ni odveč.
Poglej source. Čeprav ga bo direkt skopirat mogoče težko in predvsem sumljivo, a čisto tako za vpogled, kako je to v praksi narejeno, da dela s solidno hitrostjo mogoče ni odveč.
On the journey of life, I chose the psycho path.
kriko1 ::
Poštenost je vrlina !
Imam za domačo nalogo in za kodo ne ne bom plačal.
Lp
Cheap ass! :>
// dodamo nicle
for (int i = 0; i < poly[0]; i++)
{
bitStr += "0";
}
while (bitStr.length() >= polyStr.length())
{
String part = bitStr.substring(0, polyStr.length());
long a = Long.parseLong(part, 2);
long b = Long.parseLong(polyStr, 2);
long res = a ^ b;
bitStr = bitStr.substring(polyStr.length(), bitStr.length());
bitStr = Long.toBinaryString(res) + bitStr;
}
Tale del kode bi ti moral biti zelo razumljiv - dela tako kot se to na roke računa, obstajajo boljše poti verjetno. Če imaš poly podan kot npr. polje postavljenih bitov, ga ustrezno pretvori v bitni niz, pazi
na ničle (dolžina polinoma!) in bo vse ok.
Če rabiš nadaljno asistenco, vprašaj.
Si slučajno na koprski fak. za naravoslovje?
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | [Java] Kako izračunati hash diska.Oddelek: Programiranje | 4720 (3550) | kunigunda |
| » | java problemOddelek: Programiranje | 687 (567) | Sergio |
| » | [C++] Kopiranje char arraya v drug char arrayOddelek: Programiranje | 1186 (1057) | win64 |
| » | COM in Visual BasicOddelek: Programiranje | 2083 (1544) | pexo |
| » | branje byte[] iz MS access-ove bazeOddelek: Programiranje | 1779 (1689) | BHawk |