Page 1 of 1

Bittien murskaamis ongelma.

Posted: Thu Nov 12, 2009 10:39 pm
by JATothrim
Koodatessani kuvan pakkaus algoritmiäni törmäsin ylitse pääsemättömään brobleemaan:
Ohjelma työntää jonoon (First In, First Out. tietorakenne) n-kappaletta yksittäisiä tavuja (eli 8 bittiä per luku).
Nyt jonosta pitäisi voida ottaa n-Bittiä kerralla, ikäänkuin koko jono olisi yksi pötköbittejä, jono lyhenee tällöin n-Bittin verran. Otettu n-bittin pötkö palautetaan 32-bittisessä muuttujassa. Tästä seuraa, että yli 32 bittiä ei voida ottaa kerralla jonosta (32-bit integer). Miten tämä toteutetaan? Apuja?

Esim:
Jono enen kuin siitä otetaan bittejä pois:
tavu 1: tavu 2: tavu 3:
10110100 10101011 00100110 10010101 01111010

Otetaan 6 bittiä: "101101" ja jono lyhenee muotoon:
00 10101011 00100110 10010101 01111010

Otetaan nyt 3 bittiä: "001" ja jono lyhenee muotoon:
0101011 00100110 10010101 01111010

Otetaan jälleen 16 bittiä: "0101011 00100110 1" ja jono lyhenee muotoon:
0010101 01111010

(PS: Jostain syystä osasin tehdä bittijonooni lisäys operaation, mutta otto operaation takkuaa pahasti.)

Re: Bittien murskaamis ongelma.

Posted: Thu Nov 12, 2009 11:29 pm
by KilledWhale
JATothrim wrote:(hyminää... (olen jo lähes 100% C++/IDE konkari) :P :lol: tirsk. ketjun "pro-maisuus" on alle nollan..)
skorpioni-cb: Käännät ne käyttäen jotain vapaasti saatavilla olevaa kääntäjää. Esim MinGW (joka on siis GCC wintoosalle) paketilla onnistuu. Hyvä IDE auttaa asiassa paljon. Esim. itse käytän Code:Blocks:ia.
Kylläkait 100% C++/IDE konkari tuollaiseen pystyy? Jos suuria lukuja haluat niin c++ löytyy ainakin GMP, joka on suhteellisen helppokäyttöinen.

Re: Bittien murskaamis ongelma.

Posted: Thu Nov 12, 2009 11:45 pm
by Dibalo
Koska olet 100% C++-konkari, annan vain vinkkejä:
  • Dynaaminen muistinvaraus (esim malloc).
  • Osoitinaritmetiikka.
  • Bittioperaatiot.

Re: Bittien murskaamis ongelma.

Posted: Thu Nov 12, 2009 11:51 pm
by JATothrim
KilledWhale wrote:
JATothrim wrote:(hyminää... (olen jo lähes 100% C++/IDE konkari) :P :lol: tirsk. ketjun "pro-maisuus" on alle nollan..)
...
Kylläkait 100% C++/IDE konkari tuollaiseen pystyy? Jos suuria lukuja haluat niin c++ löytyy ainakin GMP, joka on suhteellisen helppokäyttöinen.
:D _lähes_ 100% ja en puhunut ongelman ratkaisusta. Ei hauskaa.

GMP auttaa isojen lukujen laskemisessa, mutta ei pilkkomisessa osiin. Tuota bittijonoa käsittellään siis vähän kuin merkkijonoa.

Re: Bittien murskaamis ongelma.

Posted: Fri Nov 13, 2009 3:22 pm
by skorpioni-cb
JATothrim wrote:
KilledWhale wrote:
JATothrim wrote:(hyminää... (olen jo lähes 100% C++/IDE konkari) :P :lol: tirsk. ketjun "pro-maisuus" on alle nollan..)
...
Kylläkait 100% C++/IDE konkari tuollaiseen pystyy? Jos suuria lukuja haluat niin c++ löytyy ainakin GMP, joka on suhteellisen helppokäyttöinen.
:D _lähes_ 100% ja en puhunut ongelman ratkaisusta. Ei hauskaa.

GMP auttaa isojen lukujen laskemisessa, mutta ei pilkkomisessa osiin. Tuota bittijonoa käsittellään siis vähän kuin merkkijonoa.

Lukekaa mitä nuo sanoo.

Re: Bittien murskaamis ongelma.

Posted: Fri Nov 13, 2009 5:14 pm
by Dibalo
Attention:

Noniin lapset (itseni mukaan lukien)! Tämä asiattomien kommenttien postaaminen loppuu tässä ketjussa tähän. Jos moista näkyy, niin varoituksia alkaa lennellä.

Mutta sitten itse ongelmaan. Itse suosittelisin sinua tekemään vaikka oman luokan noille "liukuville bittijonoille". Kuten aikaisemmin mainitsin, on malloc varsin sopiva tähän tilanteeseen. Konstruktori voisi vaikka ottaa vaikka halutun bittimäärän kokonaislukuina. Huomioi, että malloc voi varata minimissään täysiä tavuja, joten bittisarjojen pituus on aina 8. kertoin.

En saa antamastasi esimerkistä oikein kunnon kuvaa alogritmisi toiminnasta, mutta malloc:n palauttamaa osoitinta voidaan käyttää esimerkiksi vaikka taulukkona bytejä (unsigned char). Näin ollen voit lukea jonostasi bittejä tähän taulukkoon. Byte-order:n (little-/big-endian) voit päättää vapaasti, kannattaa tosin valita sellainen, joka sopii itsellesi paremmin. Ja malloc:n varaama muistihan pitää luonnollisesti vapauttaa lopuksi free:llä. ;) Jos haluat homman kompaktiin pakettiin, niin tiettyjen operaattoreiden (=, ==, !=, <<, >>, jne.) ei ole pahitteeksi. :)

Ja ihan vinkkinä seuraavaan kertaan: ylimielisyys kannattaa unohtaa heti alkuunsa, varsinkin, kun omalla "paremmuudella" tarkoituksella halveerataan toista tai asetetaan tämä alenevaan asemaan. Silloin on todellakin hyvä pystyä seisomaan omien sanojen takana. Muuten seuraukset ovat hyvinkin tuhoisia itsensä kannalta.