ro-eachdraidheil

Tha innealan reic den dealbhadh againn fhèin. Taobh a-staigh an Raspberry Pi agus beagan uèirleadh air bòrd air leth. Tha neach-gabhail buinn, neach-gabhail cunntasan, ionad banca ceangailte... Tha a h-uile càil fo smachd prògram fèin-sgrìobhte. Tha an eachdraidh obrach gu lèir air a sgrìobhadh gu log air draibheadh ​​​​flash (MicroSD), a thèid an uairsin a ghluasad tron ​​​​eadar-lìn (a’ cleachdadh modem USB) chun t-seirbheisiche, far a bheil e air a stòradh ann an stòr-dàta. Tha fiosrachadh reic air a luchdachadh a-steach do 1c, tha eadar-aghaidh lìn sìmplidh ann cuideachd airson sgrùdadh, msaa.

Is e sin, tha an iris deatamach - airson cunntasachd (teachd-a-steach, reic, msaa), sgrùdadh (gach seòrsa fàilligeadh agus suidheachaidhean force majeure eile); Is e seo, dh’ fhaodadh duine a ràdh, a h-uile fiosrachadh a th’ againn mun inneal seo.

duilgheadas

Tha draibhearan Flash a’ nochdadh gur e innealan fìor neo-earbsach a th’ annta. Bidh iad a 'fàilligeadh le cunbhalachd iongantach. Bidh seo a’ leantainn gu an dà chuid ùine downt inneal agus (mura b’ urrainnear an loga a ghluasad air-loidhne airson adhbhar air choireigin) gu call dàta.

Chan e seo a’ chiad eòlas air a bhith a’ cleachdadh draibhearan flash, roimhe seo bha pròiseact eile ann le còrr air ceud inneal, far an robh an iris air a stòradh air draibhearan USB flash, bha duilgheadasan ann cuideachd le earbsachd, aig amannan bha an àireamh den fheadhainn a dh’ fhàillig ann. bha mìos anns na dusan. Dh’fheuch sinn diofar dhràibhearan flash, a’ toirt a-steach feadhainn le suaicheantas le cuimhne SLC, agus tha cuid de mhodalan nas earbsaiche na cuid eile, ach cha do dh’ fhuasgail e an duilgheadas gu mòr le bhith a’ cur an àite dhràibhearan flash.

Thoir aire! Leughadh fada! Mura h-eil ùidh agad ann an “carson”, ach dìreach ann an “ciamar”, faodaidh tu a dhol dìreach Aig a’ cheann thall artaigilean.

co-dhùnadh

Is e a’ chiad rud a thig gu inntinn: trèig MicroSD, stàlaich, mar eisimpleir, SSD, agus bròg bhuaithe. Gu teòiridheach comasach, is dòcha, ach gu ìre mhath daor, agus chan eil e cho earbsach (tha inneal-atharrachaidh USB-SATA air a chur ris; chan eil staitistig fàilligeadh airson SSDs buidseit cuideachd brosnachail).

Chan eil USB HDD cuideachd a’ coimhead coltach ri fuasgladh air leth tarraingeach.

Mar sin, thàinig sinn chun roghainn seo: fàg booting bho MicroSD, ach cleachd iad ann am modh leughaidh a-mhàin, agus stòraich an loga obrachaidh (agus fiosrachadh eile a tha gun samhail airson pìos bathar-cruaidh sònraichte - àireamh sreathach, calibrations mothachaidh, msaa) an àiteigin eile .

Chaidh cuspair FS le leughadh a-mhàin airson sùbh-craoibh a sgrùdadh a-staigh agus a-muigh, cha bhith mi a’ fuireach air mion-fhiosrachadh buileachaidh san artaigil seo (ach ma tha ùidh ann, is dòcha gun sgrìobh mi mion-artaigil air a’ chuspair seo). Is e an aon phuing a bu mhath leam a thoirt fa-near gu bheil an dà chuid bho eòlas pearsanta agus bho lèirmheasan air an fheadhainn a tha air a chuir an gnìomh mar-thà, gu bheil buannachd ann an earbsachd. Tha, tha e do-dhèanta faighinn cuidhteas briseadh sìos gu tur, ach tha e comasach gu mòr am tricead a lughdachadh. Agus tha na cairtean a 'fàs aonaichte, a tha ga dhèanamh nas fhasa do luchd-seirbheis ath-nuadhachadh.

Bathar cruaidh

Cha robh teagamh sam bith ann mun roghainn seòrsa cuimhne - NOR Flash.
Argumaidean:

• ceangal sìmplidh (mar as trice am bus SPI, a tha eòlas agad mu thràth air a chleachdadh, agus mar sin chan eil dùil ri duilgheadasan bathar-cruaidh);
• prìs gòrach;
• protocol obrachaidh àbhaisteach (tha am buileachadh mar-thà anns an kernel Linux, ma thogras tu, faodaidh tu fear treas-phàrtaidh a ghabhail, a tha cuideachd an làthair, no eadhon do chuid fhèin a sgrìobhadh, gu fortanach tha a h-uile dad sìmplidh);
• earbsachd agus goireas:
  bho dhuilleag-dàta àbhaisteach: tha dàta air a stòradh airson 20 bliadhna, 100000 cearcall sguabaidh airson gach bloc;
  bho stòran treas pàrtaidh: BER gu math ìosal, a’ postadh nach eil feum air còdan ceartachaidh mhearachdan (bidh cuid de dh’ obraichean a’ beachdachadh air ECC airson NOR, ach mar as trice bidh iad fhathast a’ ciallachadh MLC NOR; bidh seo a’ tachairt cuideachd).

Bheir sinn tuairmse air na riatanasan airson meud agus goireas.

Bu mhath leam gum biodh an dàta cinnteach gun tèid a shàbhaladh airson grunn làithean. Tha seo riatanach gus nach tèid an eachdraidh reic a chall ma tha duilgheadasan conaltraidh ann. Cuiridh sinn fòcas air 5 latha, rè na h-ùine seo (eadhon a’ gabhail a-steach deireadh-sheachdainean agus saor-làithean) faodar an duilgheadas fhuasgladh.

Tha sinn an-dràsta a’ cruinneachadh mu 100kb de logaichean gach latha (3-4 mìle inntrigeadh), ach mean air mhean tha am figear seo a’ fàs - tha am mion-fhiosrachadh a’ dol am meud, tha tachartasan ùra gan cur ris. A bharrachd air an sin, uaireannan bidh spreadhaidhean ann (bidh cuid de luchd-mothachaidh a 'tòiseachadh a' spamadh le rudan ceàrr, mar eisimpleir). Obraichidh sinn airson 10 mìle clàr 100 bytes gach - megabytes gach latha.

Gu h-iomlan, thig 5MB de dhàta glan (gu math teann) a-mach. Tuilleadh dhaibh (tuairmse garbh) 1MB de dhàta seirbheis.

Is e sin, feumaidh sinn chip 8MB mura cleachd sinn teannachadh, no 4MB ma chleachdas sinn e. Àireamhan gu math fìrinneach airson an seòrsa cuimhne seo.

A thaobh a’ ghoireas: ma tha sinn an dùil gun tèid an cuimhne gu lèir ath-sgrìobhadh gun a bhith nas fhaide na aon uair gach 5 latha, an uairsin thairis air 10 bliadhna de sheirbheis gheibh sinn nas lugha na mìle cearcall ath-sgrìobhaidh.
Leig leam do chuimhneachadh gu bheil an neach-dèanamh a 'gealltainn ceud mìle.

Beagan mu NOR vs NAND

An-diugh, gu dearbh, tha cuimhne NAND tòrr nas mòr-chòrdte, ach cha bhithinn ga chleachdadh airson a’ phròiseict seo: tha NAND, eu-coltach ri NOR, gu riatanach a’ cur feum air còdan ceartachaidh mhearachdan, clàr de dhroch bhlocaichean, msaa, agus cuideachd casan nan Mar as trice bidh sgoltagan NAND tòrr a bharrachd.

Am measg eas-bhuannachdan NOR tha:

• tomhas beag (agus, a rèir sin, prìs àrd gach megabyte);
• astar conaltraidh ìosal (gu ìre mhòr air sgàth gu bheil eadar-aghaidh sreathach air a chleachdadh, mar as trice SPI no I2C);
• sguab às gu slaodach (a rèir meud a’ bhloca, bheir e bho bloigh diog gu grunn diogan).

Tha e coltach nach eil dad deatamach dhuinn, agus mar sin leanaidh sinn oirnn.

Ma tha am mion-fhiosrachadh inntinneach, chaidh am microcircuit a thaghadh aig 25df321a (ge-tà, tha seo neo-chudromach, tha tòrr analogues air a’ mhargaidh a tha co-chosmhail ri pinout agus siostam àithne; eadhon ged a tha sinn airson microcircuit a chuir a-steach bho neach-dèanamh eadar-dhealaichte agus / no meud eadar-dhealaichte, obraichidh a h-uile càil gun a bhith ag atharrachadh an còd).

Bidh mi a’ cleachdadh an draibhear a chaidh a thogail a-steach don kernel Linux; air Raspberry, le taing dha taic ath-chòmhdach craoibhe inneal, tha a h-uile dad gu math sìmplidh - feumaidh tu an ath-chòmhdach cruinnichte a chuir a-steach / boot/overlays agus beagan atharrachadh /boot/config.txt.

Eisimpleir faidhle dts

Gus a bhith onarach, chan eil mi cinnteach gu bheil e sgrìobhte gun mhearachdan, ach tha e ag obair.

/*
 * Device tree overlay for at25 at spi0.1
 */

/dts-v1/;
/plugin/;

/ {
    compatible = "brcm,bcm2835", "brcm,bcm2836", "brcm,bcm2708", "brcm,bcm2709"; 

    /* disable spi-dev for spi0.1 */
    fragment@0 {
        target = <&spi0>;
        __overlay__ {
            status = "okay";
            spidev@1{
                status = "disabled";
            };
        };
    };

    /* the spi config of the at25 */
    fragment@1 {
        target = <&spi0>;
        __overlay__ {
            #address-cells = <1>;
            #size-cells = <0>;
            flash: m25p80@1 {
                    compatible = "atmel,at25df321a";
                    reg = <1>;
                    spi-max-frequency = <50000000>;

                    /* default to false:
                    m25p,fast-read ;
                    */
            };
        };
    };

    __overrides__ {
        spimaxfrequency = <&flash>,"spi-max-frequency:0";
        fastread = <&flash>,"m25p,fast-read?";
    };
};

Agus loidhne eile ann an config.txt

dtoverlay=at25:spimaxfrequency=50000000

Fàgaidh mi an tuairisgeul mu bhith a’ ceangal a’ chip ris an Raspberry Pi. Air an aon làimh, chan eil mi nam eòlaiche ann an electronics, air an làimh eile, tha a h-uile dad an seo banal eadhon dhòmhsa: chan eil ach casan 8 aig a ’microcircuit, agus feumaidh sinn talamh, cumhachd, SPI (CS, SI, SO, SCK) ); tha na h-ìrean an aon rud ris an fheadhainn aig an Raspberry Pi, chan eil feum air uèirleadh a bharrachd - dìreach ceangail na prìnichean 6 comharraichte.

Aithris dhuilgheadas

Mar as àbhaist, bidh aithris na trioblaid a’ dol tro ghrunn thursan, agus tha e coltach riumsa gu bheil an t-àm ann airson an ath fhear. Mar sin stadamaid, cuir ri chèile na chaidh a sgrìobhadh mu thràth, agus soilleireachadh am mion-fhiosrachadh a tha air fhàgail san dubhar.

Mar sin, tha sinn air co-dhùnadh gum bi an loga air a stòradh ann an SPI NOR Flash.

Dè a th’ ann an NOR Flash dhaibhsan aig nach eil fios?

Is e cuimhne neo-luaineach a tha seo leis an urrainn dhut trì obrachaidhean a dhèanamh:

1. Leughadh:
   An leughadh as cumanta: bidh sinn a’ sgaoileadh an t-seòlaidh agus a’ leughadh na h-uimhir de bytes a dh’ fheumas sinn;
2. Clàradh:
   Tha sgrìobhadh gu NOR flash coltach ri fear àbhaisteach, ach tha aon rud sònraichte ann: chan urrainn dhut ach 1 gu 0 atharrachadh, ach chan ann a chaochladh. Mar eisimpleir, nam biodh 0x55 againn ann an cealla cuimhne, an uairsin às deidh dhuinn 0x0f a sgrìobhadh thuige, bidh 0x05 air a stòradh an sin mu thràth (faic an clàr gu h-ìosal);
3. Cuir às:
   Gu dearbh, feumaidh sinn a bhith comasach air an obair eile a dhèanamh - atharraich 0 gu 1, is e seo dìreach airson a tha an obair sguabaidh. Eu-coltach ris a 'chiad dhà, bidh e ag obrachadh chan ann le bytes, ach le blocaichean (is e 4kb am bloc sguabaidh as lugha anns a' chip taghte). Bidh Erase a 'sgrios a' bhloc gu lèir agus is e an aon dòigh air atharrachadh 0 gu 1. Mar sin, nuair a bhios tu ag obair le cuimhne flash, gu tric feumaidh tu structaran dàta a cho-thaobhadh ris a 'chrìoch bloca sguabaidh.
   Clàradh ann an NOR Flash:

Dàta binary

Bha
01010101

Air a chlàradh
00001111

Air fàs
00000101

Tha an log fhèin a’ riochdachadh sreath de chlàran de dh’fhaid caochlaideach. Tha fad àbhaisteach clàr timcheall air 30 bytes (ged a bhios clàran a tha grunn kilobytes de dh'fhaid uaireannan a’ nochdadh). Anns a 'chùis seo, bidh sinn ag obair còmhla riutha dìreach mar sheata de bytes, ach, ma tha ùidh agad, tha CBOR air a chleachdadh taobh a-staigh nan clàran

A bharrachd air an loga, feumaidh sinn beagan fiosrachaidh “suidheachadh” a stòradh, an dà chuid ùrachadh agus nach eil: ID inneal sònraichte, calibrations mothachaidh, bratach “inneal air a chiorramachadh airson ùine”, msaa.
Tha am fiosrachadh seo na sheata de chlàran prìomh luach, cuideachd air an stòradh ann an CBOR. Chan eil mòran den fhiosrachadh seo againn (beagan kilobytes aig a’ char as motha), agus is ann ainneamh a thèid ùrachadh.
Anns na leanas canaidh sinn co-theacs ris.

Ma chuimhnicheas sinn far an do thòisich an artaigil seo, tha e glè chudromach dèanamh cinnteach à stòradh dàta earbsach agus, ma ghabhas e dèanamh, obrachadh leantainneach eadhon ma dh’ fhàillig bathar-cruaidh / coirbeachd dàta.

Dè na stòran de dhuilgheadasan air am faodar beachdachadh?

• Cuir dheth cumhachd rè obair sgrìobhaidh / sguabaidh às. Tha seo bhon roinn “chan eil cleas an-aghaidh crowbar.”
  Fiosrachadh bho còmhraidhean air stackexchange: nuair a thèid an cumhachd a chuir dheth fhad ‘s a tha thu ag obair le flash, bidh an dà chuid cuir às (suidhichte gu 1) agus sgrìobh (suidhich gu 0) a’ leantainn gu giùlan neo-mhìnichte: faodar dàta a sgrìobhadh, ann am pàirt sgrìobhte (can, ghluais sinn 10 bytes / 80 bits , ach chan eil e comasach fhathast 45 pìosan a sgrìobhadh), tha e comasach cuideachd gum bi cuid de na pìosan ann an staid “meadhanach” (faodaidh leughadh an dà chuid 0 agus 1 a thoirt gu buil);
• Mearachdan sa chuimhne flash fhèin.
  Chan urrainn dha BER, ged a tha e glè ìosal, a bhith co-ionann ri neoni;
• Mearachdan bus
  Chan eil dàta a thèid a ghluasad tro SPI air a dhìon ann an dòigh sam bith; faodaidh an dà chuid mearachdan aon-phìos agus mearachdan sioncronaidh tachairt - call no cuir a-steach pìosan (a dh’ adhbhraicheas saobhadh dàta mòr);
• Mearachdan/glitches eile
  Mearachdan sa chòd, glitches sùbh-craoibhe, eadar-theachd coimheach ...

Tha mi air na riatanasan a chuir ri chèile, agus tha feum air an coileanadh, nam bheachd-sa, gus dèanamh cinnteach à earbsachd:

• feumaidh clàran a dhol a-steach don chuimhne flash sa bhad, chan eilear a’ beachdachadh air sgrìobhaidhean dàil; - ma thachras mearachd, feumar a lorg agus a phròiseasadh cho tràth ‘s a ghabhas; - feumaidh an siostam, ma ghabhas e dèanamh, faighinn seachad air mearachdan.
  (eisimpleir bho bheatha “mar nach bu chòir dha a bhith”, a tha mi a’ smaoineachadh a choinnich a h-uile duine: às deidh ath-thòiseachadh èiginneach, tha an siostam faidhle “briste” agus chan eil an siostam obrachaidh a ’brògadh)

Beachdan, dòighean-obrach, meòrachadh

Nuair a thòisich mi a’ smaoineachadh mun duilgheadas seo, chaidh tòrr bheachdan tro mo cheann, mar eisimpleir:

• cleachdadh dlùthadh dàta;
• cleachd structaran dàta ciallach, mar eisimpleir, a 'stòradh cinn clàran air leth bho na clàran fhèin, gus an urrainn dhut an còrr a leughadh gun duilgheadas sam bith ma tha mearachd ann an clàr sam bith;
• cleachd raointean bit gus smachd a chumail air crìoch a chuir air clàradh nuair a thèid an cumhachd a chuir dheth;
• stòradh checksums airson a h-uile càil;
• cleachd seòrsa de chòd dìon-fuaim.

Chaidh cuid de na beachdan sin a chleachdadh, agus chaidh co-dhùnadh cuid eile a thrèigsinn. Rachamaid ann an òrdugh.

Dùmhlachd dàta

Tha na tachartasan fhèin a tha sinn a’ clàradh anns an iris gu math coltach agus ath-aithris (“thilg bonn 5 rubles”, “brùth am putan airson atharrachadh a thoirt seachad”, ...). Mar sin, bu chòir teannachadh a bhith gu math èifeachdach.

Tha an teannachadh os cionn beag beag (tha am pròiseasar againn gu math cumhachdach, bha aon chridhe aig eadhon a’ chiad Pi le tricead 700 MHz, tha grunn choraichean aig modalan gnàthach le tricead thairis air gigahertz), tha an ìre iomlaid leis an stòradh ìosal (grunn megabytes gach diog), tha meud nan clàran beag. San fharsaingeachd, ma bheir teannachadh buaidh air coileanadh, cha bhi e ach deimhinneach. (gu tur neo-bhreithneachail, dìreach ag ràdh). A bharrachd air an sin, chan eil fìor freumhachadh againn, ach Linux cunbhalach - mar sin cha bu chòir gum biodh feum air mòran oidhirp air a bhuileachadh (tha e gu leòr dìreach an leabharlann a cheangal agus grunn ghnìomhan a chleachdadh bhuaithe).

Chaidh pìos den log a thoirt bho inneal obrach (1.7 MB, 70 mìle inntrigeadh) agus chaidh a sgrùdadh an-toiseach airson compressibility a’ cleachdadh gzip, lz4, lzop, bzip2, xz, zstd ri fhaighinn air a’ choimpiutair.

• sheall gzip, xz, zstd toraidhean co-chosmhail (40Kb).
  Chuir e iongnadh orm gun do sheall an xz fasanta e fhèin an seo aig ìre gzip no zstd;
• thug lzip le roghainnean bunaiteach toraidhean beagan nas miosa;
• Cha do sheall lz4 agus lzop toraidhean fìor mhath (150Kb);
• sheall bzip2 toradh iongantach math (18Kb).

Mar sin, tha an dàta air a dhlùthadh gu math.
Mar sin (mura lorg sinn lochdan marbhtach) bidh teannachadh ann! Dìreach air sgàth 's gum faod barrachd dàta a bhith a' freagairt air an aon dhràibhear flash.

Leig dhuinn smaoineachadh mu na h-eas-bhuannachdan.

A 'chiad dhuilgheadas: tha sinn air aontachadh mar-thà gum feum a h-uile clàr a dhol gu flash sa bhad. Mar as trice, bidh an tasglann a’ cruinneachadh dàta bhon t-sruth a-steach gus an co-dhùin e gu bheil an t-àm ann sgrìobhadh air an deireadh-sheachdain. Feumaidh sinn bloca dàta teann fhaighinn sa bhad agus a stòradh ann an cuimhne neo-luaineach.

Chì mi trì dòighean:

1. Dèan teannachadh air gach clàr a’ cleachdadh teannachadh faclair an àite na h-algorithms a chaidh a dheasbad gu h-àrd.
   Tha e na roghainn gu tur obrachail, ach cha toil leam e. Gus dèanamh cinnteach gum bi ìre teannachaidh nas fheàrr no nas lugha, feumaidh am faclair a bhith “air a dhealbhadh” gu dàta sònraichte; bidh atharrachadh sam bith a’ leantainn gu tuiteam gu tubaisteach aig an ìre teannachaidh. Seadh, faodar an duilgheadas fhuasgladh le bhith a’ cruthachadh dreach ùr den fhaclair, ach is e ceann goirt a tha seo - feumaidh sinn a h-uile dreach den fhaclair a stòradh; anns gach inntrigeadh feumaidh sinn innse dè an dreach den fhaclair a chaidh a dhlùthadh...
2. Dèan teannachadh air gach clàr a’ cleachdadh algorithms “clasaigeach”, ach gu neo-eisimeileach bhon fheadhainn eile.
   Chan eil na h-algorithms teannachaidh air a bheilear a’ beachdachadh air an dealbhadh gus obrachadh le clàran den mheud seo (deichean de bytes), bidh e soilleir gum bi an co-mheas teannachaidh nas lugha na 1 (is e sin, àrdachadh meud dàta an àite teannachadh);
3. Dèan FLUSH às deidh gach clàradh.
   Tha taic aig mòran de leabharlannan teannachaidh airson FLUSH. Is e seo àithne (no paramadair don mhodh teannachaidh), nuair a gheibh e sin bidh an tasglann a’ cruthachadh sruth teann gus an gabh a chleachdadh airson ath-nuadhachadh uile dàta neo-dhùmhlaichte a chaidh fhaighinn mu thràth. A leithid de analogues sync ann an siostaman faidhle no commit ann an sql.
   Is e an rud a tha cudromach gum bi e comasach do ghnìomhachd teannachaidh às deidh sin am faclair cruinnichte a chleachdadh agus nach bi an co-mheas teannachaidh a’ fulang cho mòr ris an dreach roimhe.

Tha mi a’ smaoineachadh gu bheil e follaiseach gun do thagh mi an treas roghainn, leig dhuinn sùil nas mionaidiche a thoirt air.

Fhuaras artaigil sgoinneil mu dheidhinn FLUSH ann an zlib.

Rinn mi deuchainn glùin stèidhichte air an artaigil, thug mi 70 mìle inntrigeadh log bho inneal fìor, le meud duilleag de 60Kb (tillidh sinn gu meud na duilleige nas fhaide air adhart) fhuair:

Fiosrachadh cruaidh
Compression gzip -9 (gun FLUSH)
zlib le Z_PARTIAL_FLUSH
zlib le Z_SYNC_FLUSH

Meud, KB
1692
40
352
604

Aig a’ chiad sealladh, tha a’ phrìs a chuir FLUSH a-steach ro àrd, ach ann an da-rìribh chan eil mòran roghainn againn - an dàrna cuid gun a bhith a’ teannachadh idir, no a bhith a’ teannachadh (agus gu h-èifeachdach) le FLUSH. Cha bu chòir dhuinn dìochuimhneachadh gu bheil 70 mìle clàr againn, chan eil an call obrach a thug Z_PARTIAL_FLUSH a-steach ach 4-5 bytes gach clàr. Agus thionndaidh an co-mheas teannachaidh gu bhith cha mhòr 5: 1, a tha nas motha na toradh sàr-mhath.

Is dòcha gum bi e na iongnadh, ach tha Z_SYNC_FLUSH gu dearbh na dhòigh nas èifeachdaiche air FLUSH a dhèanamh

Nuair a bhios tu a’ cleachdadh Z_SYNC_FLUSH, bidh na 4 bytes mu dheireadh de gach inntrigeadh an-còmhnaidh 0x00, 0x00, 0xff, 0xff. Agus ma tha sinn eòlach orra, chan fheum sinn an stòradh, agus mar sin chan eil am meud mu dheireadh ach 324Kb.

Tha mìneachadh san artaigil ris an do rinn mi ceangal:

Tha bloc seòrsa 0 ùr le susbaint falamh air a chur ris.

Ann am bloc seòrsa 0 le susbaint falamh tha:

• am bann-cinn trì-phìos;
• 0 gu 7 pìosan co-ionann ri neoni, gus co-thaobhadh byte a choileanadh;
• an sreath ceithir-byte 00 00 FF FF.

Mar a chì thu gu furasta, anns a’ bhloc mu dheireadh ro na 4 bytes sin tha bho 3 gu 10 pìosan neoni. Ach, tha cleachdadh air sealltainn gu bheil co-dhiù 10 pìosan neoni ann.

Tha e a 'tionndadh a-mach gu bheil a leithid de bhlocaichean goirid de dhàta mar as trice (an-còmhnaidh?) air an còdachadh le bhith a' cleachdadh bloc de sheòrsa 1 (bloc stèidhichte), a tha gu riatanach a 'crìochnachadh le 7 pìosan neoni, a' toirt seachad 10-17 pìosan neoni cinnteach (agus an còrr. a bhith neoni le coltachd de mu 50%).

Mar sin, air dàta deuchainn, ann an 100% de chùisean tha aon byte neoni ro 0x00, 0x00, 0xff, 0xff, agus ann an còrr air trian de chùisean tha dà neoni bytes ann. (is dòcha gur e an fhìrinn gu bheil mi a 'cleachdadh CBOR binary, agus nuair a bhios mi a' cleachdadh teacsa JSON, bhiodh blocaichean de sheòrsa 2 - bloc fiùghantach nas cumanta, fa leth, blocaichean gun neoni bytes a bharrachd ro 0x00, 0x00, 0xff, 0xff bhiodh iad a 'tachairt).

Gu h-iomlan, a’ cleachdadh an dàta deuchainn a tha ri fhaighinn, tha e comasach faighinn a-steach do nas lugha na 250Kb de dhàta teann.

Faodaidh tu beagan a bharrachd a shàbhaladh le bhith a ’dèanamh beagan juggling: airson a-nis bidh sinn a’ seachnadh làthaireachd beagan phìosan neoni aig deireadh a ’bhloc, chan eil cuid de phìosan aig toiseach a’ bhloc cuideachd ag atharrachadh ...
Ach an uairsin rinn mi co-dhùnadh làidir airson stad, air neo aig an ìre seo b’ urrainn dhomh an tasglann agam fhìn a leasachadh.

Gu h-iomlan, bhon dàta deuchainn agam fhuair mi 3-4 bytes gach sgrìobhadh, thionndaidh an co-mheas teannachaidh a-mach gu bhith nas àirde na 6: 1. Bidh mi onarach: cha robh dùil agam ri leithid de thoradh; nam bheachd-sa, tha dad nas fheàrr na 2: 1 mar thoradh mar-thà a tha a’ fìreanachadh cleachdadh teannachaidh.

Tha a h-uile dad gu math, ach tha zlib (deflate) fhathast na algairim teannachaidh àrsaidh, airidh air agus beagan seann-fhasanta. Tha an fhìrinn gu bheil an 32Kb mu dheireadh den t-sruth dàta neo-bhrùichte air a chleachdadh mar fhaclair a’ coimhead neònach an-diugh (is e sin, ma tha cuid de bhloca dàta glè choltach ris na bha san t-sruth cuir a-steach 40Kb air ais, tòisichidh e air a thasgadh a-rithist, agus cha toir e iomradh air tachartas roimhe). Ann an tasglannan fasanta an latha an-diugh, bidh meud an fhaclair gu tric air a thomhas ann am megabytes seach kilobytes.

Mar sin leanaidh sinn ar mion-sgrùdadh air tasglannan.

An uairsin rinn sinn deuchainn air bzip2 (cuimhnich, às aonais FLUSH sheall e co-mheas teannachaidh math faisg air 100: 1). Gu mì-fhortanach, rinn e glè dhroch le FLUSH; bha meud an dàta teannachaidh nas motha na an dàta neo-bhrùichte.

Na barailean agam mu na h-adhbharan airson an fhàilligeadh

Chan eil Libbz2 a’ tabhann ach aon roghainn flush, a tha coltach gu bheil e a’ glanadh am faclair (co-chosmhail ri Z_FULL_FLUSH ann an zlib); chan eilear a’ bruidhinn air teannachadh èifeachdach às deidh seo.

Agus b’ e zstd am fear mu dheireadh a chaidh a dhearbhadh. A rèir nam paramadairean, bidh e a ’teannachadh an dàrna cuid aig ìre gzip, ach fada nas luaithe, no nas fheàrr na gzip.

Gu mì-fhortanach, le FLUSH cha do rinn e glè mhath: bha meud an dàta teannachaidh timcheall air 700Kb.

Я dh'fhaighnich ceist air duilleag github a’ phròiseict, fhuair mi freagairt gum bu chòir dhut cunntadh air suas ri 10 bytes de dhàta seirbheis airson gach bloca de dhàta teann, a tha faisg air na toraidhean a fhuaireadh; chan eil dòigh ann grèim fhaighinn air deflate.

Cho-dhùin mi stad aig an ìre seo anns na deuchainnean agam le tasglannan (leig dhomh do chuir an cuimhne nach do sheall xz, lzip, lzo, lz4 iad fhèin eadhon aig an ìre deuchainn às aonais FLUSH, agus cha do bheachdaich mi air algorithms teannachaidh nas annasaiche).

Rachamaid air ais gu duilgheadasan tasglann.

Is e an dàrna duilgheadas (mar a chanas iad ann an òrdugh, chan ann ann an luach) gu bheil an dàta teannachaidh na aon shruth, anns a bheil an-còmhnaidh iomraidhean air earrannan roimhe. Mar sin, ma thèid earrann de dhàta teann a mhilleadh, bidh sinn a’ call chan e a-mhàin am bloca co-cheangailte de dhàta neo-bhrùichte, ach cuideachd a h-uile gin às deidh sin.

Tha dòigh ann airson an duilgheadas seo fhuasgladh:

1. Cuir casg air an duilgheadas bho bhith a’ tachairt - cuir cus feum air an dàta teann, a leigeas leat mearachdan aithneachadh agus a cheartachadh; bruidhnidh sinn mu dheidhinn seo nas fhaide air adhart;
2. Lùghdaich buaidhean ma tha duilgheadas ann
   Tha sinn mu thràth air a ràdh na bu thràithe gun urrainn dhut gach bloc dàta a dhlùthadh gu neo-eisimeileach, agus falbhaidh an duilgheadas leis fhèin (bidh milleadh air dàta aon bhloca a’ leantainn gu call dàta a-mhàin airson a ’bhloc seo). Ach, is e fìor chùis a tha seo far nach bi teannachadh dàta neo-èifeachdach. An fhìor cheann eile: cleachd a h-uile 4MB den chip againn mar aon thasglann, a bheir dhuinn teannachadh sàr-mhath, ach builean tubaisteach gun fhios nach bi truailleadh dàta ann.
   Tha, tha feum air co-rèiteachadh a thaobh earbsachd. Ach feumaidh sinn cuimhneachadh gu bheil sinn a’ leasachadh cruth stòraidh dàta airson cuimhne neo-luaineach le BER gu math ìosal agus ùine stòraidh dàta dearbhte de 20 bliadhna.

Rè na deuchainnean, fhuair mi a-mach gu bheil call mòr no nas lugha anns an ìre teannachaidh a’ tòiseachadh air blocaichean de dhàta teannachaidh nas lugha na 10 KB ann am meud.
Chaidh iomradh a thoirt roimhe gu bheil duilleag air a’ chuimhne a thathar a’ cleachdadh; chan eil mi a’ faicinn adhbhar carson nach bu chòir an conaltradh “aon duilleag - aon bhloca de dhàta teannachaidh” a chleachdadh.

Is e sin, is e 16Kb am meud duilleag reusanta as ìsle (le tèarmann airson fiosrachadh seirbheis). Ach, tha meud duilleag cho beag a’ cur bacadh mòr air a’ mheud clàraidh as àirde.

Ged nach eil mi fhathast a 'sùileachadh clàran nas motha na beagan kilobytes ann an cruth teann, chuir mi romhpa duilleagan 32Kb a chleachdadh (airson duilleagan 128 gu h-iomlan gach sgiob).

Geàrr-chunntas:

• Bidh sinn a’ stòradh dàta teannaichte le bhith a’ cleachdadh zlib (deflate);
• Airson gach inntrigeadh shuidhich sinn Z_SYNC_FLUSH;
• Airson gach clàr teannachaidh, bidh sinn a 'gearradh nam bytes air falbh (me 0x00, 0x00, 0xff, 0xff); anns a' cheann-cinn tha sinn a' sealltainn cia mheud bytes a gheàrr sinn dheth;
• Bidh sinn a’ stòradh dàta ann an duilleagan 32Kb; tha aon shruth de dhàta teannaichte am broinn na duilleige; Air gach duilleag bidh sinn a’ tòiseachadh air teannachadh a-rithist.

Agus, mus cuir thu crìoch air le teannachadh, bu mhath leam d ’aire a tharraing chun fhìrinn nach eil againn ach beagan bytes de dhàta teannachaidh gach clàr, agus mar sin tha e air leth cudromach gun a bhith ag àrdachadh fiosrachadh na seirbheis, tha a h-uile byte a’ cunntadh an seo.

A’ stòradh cinn-cinn dàta

Leis gu bheil clàran againn de dh'fhaid caochlaideach, feumaidh sinn dòigh air choireigin suidheachadh/crìochan chlàran a dhearbhadh.

Tha fios agam air trì dòighean-obrach:

1. Tha a h-uile clàr air a stòradh ann an sruth leantainneach, an toiseach tha bann-cinn clàraidh anns a bheil an fhaid, agus an uairsin an clàr fhèin.
   Anns an sgeadachadh seo, faodaidh an dà chuid cinn agus dàta a bhith de dh'fhaid caochlaideach.
   Gu bunaiteach, gheibh sinn liosta aon-cheangailte a tha air a chleachdadh fad na h-ùine;
2. Bidh cinn-cinn agus na clàran fhèin air an stòradh ann an sruthan fa leth.
   Le bhith a’ cleachdadh bannan-cinn seasmhach, bidh sinn a’ dèanamh cinnteach nach toir milleadh air aon cheann-cinn buaidh air an fheadhainn eile.
   Tha dòigh-obrach coltach ris air a chleachdadh, mar eisimpleir, ann an iomadh siostam faidhle;
3. Tha clàran air an stòradh ann an sruth leantainneach, tha crìoch a’ chlàir air a dhearbhadh le comharra sònraichte (caractar / sreath de charactaran a tha toirmisgte taobh a-staigh blocaichean dàta). Ma tha comharradh taobh a-staigh a 'chlàir, an uairsin cuiridh sinn sreath eile na àite (teich e).
   Tha dòigh-obrach coltach ris air a chleachdadh, mar eisimpleir, ann am protocol PPP.

Seallaidh mi.

Roghainn 1:

Tha a h-uile dad gu math sìmplidh an seo: le fios fad a ’chlàir, is urrainn dhuinn seòladh an ath chinn a thomhas. Mar sin gluaisidh sinn tro na cinn gus an coinnich sinn ri raon làn de 0xff (raon an-asgaidh) no deireadh na duilleige.

Roghainn 2:

Air sgàth cho fada ‘s a tha an clàr caochlaideach, chan urrainn dhuinn innse ro-làimh cia mheud clàr (agus mar sin bann-cinn) a dh’ fheumas sinn airson gach duilleag. Faodaidh tu na cinn-cinn agus an dàta iad fhèin a sgaoileadh thairis air diofar dhuilleagan, ach is fheàrr leam dòigh-obrach eadar-dhealaichte: bidh sinn a’ cur an dà chuid na cinn agus an dàta air aon duilleag, ach tha na cinn-cinn (de mheud cunbhalach) a’ tighinn bho thoiseach na duilleige, agus an tha dàta (de dh'fhaid caochlaideach) a' tighinn bhon deireadh. Cho luath ‘s a bhios iad“ a ’coinneachadh” (chan eil àite gu leòr ann airson inntrigeadh ùr), tha sinn den bheachd gu bheil an duilleag seo coileanta.

Roghainn 3:

Chan eil feum air an fhaid no fiosrachadh eile a stòradh mu shuidheachadh an dàta anns a ’cheann; tha comharran a’ comharrachadh crìochan nan clàran gu leòr. Ach, feumar an dàta a phròiseasadh nuair a thathar a’ sgrìobhadh/leughadh.
Chleachdainn 0xff mar chomharradh (a lìonas an duilleag às deidh a dhubhadh às), agus mar sin cha tèid an raon an-asgaidh a làimhseachadh mar dhàta.

Clàr coimeas:

Roghainn 1
Roghainn 2
Roghainn 3

Fulangas mearachd
-
+
+

Compactness
+
-
+

Iom-fhillteachd buileachaidh
*
**
**

Tha locht marbhtach air Roghainn 1: ma thèid gin de na cinn a mhilleadh, thèid an t-sreath gu lèir a sgrios. Leigidh na roghainnean a tha air fhàgail dhut beagan dàta fhaighinn air ais eadhon ma tha milleadh mòr ann.
Ach an seo tha e iomchaidh cuimhneachadh gun do chuir sinn romhainn an dàta a stòradh ann an cruth teann, agus mar sin bidh sinn a’ call an dàta gu lèir air an duilleag às deidh clàr “briste”, agus mar sin ged a tha minus sa chlàr, cha bhith sinn thoir an aire dha.

Compactness:

• anns a 'chiad roghainn, feumaidh sinn an fhaid a stòradh a-mhàin anns a' bhann-cinn; ma chleachdas sinn àireamhairean de dh'fhaid caochlaideach, sa mhòr-chuid de chùisean gheibh sinn seachad le aon byte;
• anns an dàrna roghainn feumaidh sinn an seòladh tòiseachaidh agus an fhad a stòradh; feumaidh an clàr a bhith de mheud cunbhalach, tha mi a 'toirt tuairmse air 4 bytes gach clàr (dà bytes airson a' chothromachadh, agus dà bytes airson an fhaid);
• chan fheum an treas roghainn ach aon charactar gus toiseach a’ chlàraidh a chomharrachadh, agus àrdaichidh an clàradh fhèin 1-2% air sgàth dìon. San fharsaingeachd, timcheall air co-ionannachd leis a’ chiad roghainn.

An toiseach, bheachdaich mi air an dàrna roghainn mar am prìomh fhear (agus eadhon sgrìobh e am buileachadh). Cha do thrèig mi e ach nuair a cho-dhùin mi mu dheireadh teannachadh a chleachdadh.

Is dòcha aon latha gun cleachd mi an aon roghainn fhathast. Mar eisimpleir, ma dh'fheumas mi dèiligeadh ri stòradh dàta airson bàta a tha a 'siubhal eadar an Talamh agus Mars, bidh riatanasan gu tur eadar-dhealaichte ann airson earbsachd, rèididheachd cosmaigeach, ...

A thaobh an treas roghainn: thug mi dà rionnag dha airson an duilgheadas a thaobh buileachadh dìreach air sgàth 's nach toil leam a bhith a' cluich le dìon, ag atharrachadh an fhaid sa phròiseas, msaa. Tha, is dòcha gu bheil mi claon, ach feumaidh mi an còd a sgrìobhadh - carson a bheir thu ort rudeigin a dhèanamh nach toil leat.

Geàrr-chunntas: Bidh sinn a’ taghadh an roghainn stòraidh ann an cruth slabhraidhean “ceann-cinn le faid - dàta de dh’ fhaid caochlaideach" air sgàth èifeachdas agus furasta a bhuileachadh.

A’ cleachdadh Bit Fields gus sùil a chumail air soirbheachas gnìomhachd sgrìobhaidh

Chan eil cuimhne agam a-nis càite an d’ fhuair mi am beachd, ach tha e a’ coimhead rudeigin mar seo:
Airson gach inntrigeadh, bidh sinn a 'riarachadh grunn phìosan airson brataichean a stòradh.
Mar a thuirt sinn na bu tràithe, an dèidh a sguabadh às a h-uile pìosan a lìonadh le 1s, agus faodaidh sinn atharrachadh 1 gu 0, ach chan ann a chaochladh. Mar sin airson “chan eil a’ bhratach air a suidheachadh” bidh sinn a’ cleachdadh 1, airson “tha a’ bhratach suidhichte” bidh sinn a’ cleachdadh 0.

Seo cò ris a dh’ fhaodadh a bhith a’ cur clàr de dh’fhaid caochlaideach ann am flash coltach:

1. Suidhich a’ bhratach “tha clàradh faid air tòiseachadh”;
2. Clàraich an fhaid;
3. Suidhich am bratach “tha clàradh dàta air tòiseachadh”;
4. Bidh sinn a’ clàradh dàta;
5. Suidhich a’ bhratach “crìochnaichte clàraidh”.

A bharrachd air an sin, bidh bratach “Thachair mearachd” againn, airson brataichean 4 bit gu h-iomlan.

Anns a 'chùis seo, tha dà stàite seasmhach againn "1111" - chan eil clàradh air tòiseachadh agus "1000" - bha clàradh soirbheachail; ma thachras briseadh ris nach robh dùil sa phròiseas clàraidh, gheibh sinn stàitean eadar-mheadhanach, as urrainn dhuinn an uairsin a lorg agus a phròiseasadh.

Tha an dòigh-obrach inntinneach, ach chan eil e a 'dìon ach an aghaidh briseadh cumhachd gu h-obann agus fàilligeadh coltach ris, a tha, gu dearbh, cudromach, ach tha seo fada bhon aon adhbhar (no eadhon am prìomh) airson fàilligidhean a dh'fhaodadh a bhith ann.

Geàrr-chunntas: Rachamaid air adhart a 'lorg fuasgladh math.

Checksums

Bidh checksums cuideachd ga dhèanamh comasach dèanamh cinnteach (le coltachd reusanta) gu bheil sinn a’ leughadh dìreach na bu chòir a bhith sgrìobhte. Agus, eu-coltach ris na raointean beaga air an deach beachdachadh gu h-àrd, bidh iad an-còmhnaidh ag obair.

Ma bheachdaicheas sinn air an liosta de thùsan dhuilgheadasan air an do bhruidhinn sinn gu h-àrd, bidh e comasach don t-seic mearachd aithneachadh ge bith cò às a thàinig e. (ach a-mhàin, is dòcha, airson coigrich droch-rùnach - faodaidh iad an checksum a chruthachadh cuideachd).

Mar sin mas e ar n-amas dearbhadh gu bheil an dàta slàn, is e deagh bheachd a th’ ann an checksums.

Cha do thog an roghainn algairim airson àireamhachadh an t-seic ceist sam bith - CRC. Air an aon làimh, tha feartan matamataigeach ga dhèanamh comasach cuid de mhearachdan a ghlacadh 100%; air an làimh eile, air dàta air thuaiream mar as trice bidh an algairim seo a ’sealltainn coltachd tubaistean nach eil mòran nas àirde na a’ chrìoch teòiridheach. . Is dòcha nach e seo an algairim as luaithe, agus chan e an-còmhnaidh an ìre as ìsle a thaobh an àireamh de thubaistean, ach tha càileachd fìor chudromach aige: anns na deuchainnean a choinnich mi, cha robh pàtrain sam bith ann far an do dh'fhàillig e gu soilleir. Is e seasmhachd am prìomh chàileachd sa chùis seo.

Eisimpleir de sgrùdadh tomhas-lìonaidh: pàirt de 1, pàirt de 2 (ceanglaichean gu narod.ru, duilich).

Ach, chan eil an obair airson checksum a thaghadh coileanta; Tha CRC na theaghlach iomlan de checksums. Feumaidh tu co-dhùnadh mun fhad, agus an uairsin tagh polynomial.

Chan e ceist cho sìmplidh a th’ ann a bhith a’ taghadh fad an t-seic mar a tha e coltach aig a’ chiad sealladh.

Leig leam sealltainn:
Leig leinn gu bheil coltachd mearachd anns gach byte agus fìor dheagh sgrùdadh, leig dhuinn obrachadh a-mach an àireamh chuibheasach de mhearachdan gach millean clàr:

Dàta, byte
Checksum, byte
Mearachdan neo-aithnichte
Lorgaidh mearachdan meallta
Dearbhaidhean meallta iomlan

1
0
1000
0
1000

1
1
4
999
1003

1
2
≈ 0
1997
1997

1
4
≈ 0
3990
3990

10
0
9955
0
9955

10
1
39
990
1029

10
2
≈ 0
1979
1979

10
4
≈ 0
3954
3954

1000
0
632305
0
632305

1000
1
2470
368
2838

1000
2
10
735
745

1000
4
≈ 0
1469
1469

Bhiodh e coltach gu bheil a h-uile dad sìmplidh - a rèir dè cho fada ‘s a tha an dàta air a dhìon, tagh fad an t-seic leis a’ char as lugha de nithean ceàrr - agus tha an cleas anns a ’bhaga.

Ach, tha duilgheadas ag èirigh le sgrùdaidhean goirid: ged a tha iad math air mearachdan aon-phìos a lorg, faodaidh iad le coltachd gu math àrd gabhail ri dàta gu tur air thuaiream mar a tha ceart. Bha artaigil ann mu thràth air Habré a’ toirt cunntas air duilgheadas ann am fìor bheatha.

Mar sin, gus dèanamh cinnteach gu bheil maids dearbhaidh air thuaiream cha mhòr do-dhèanta, feumaidh tu checksums a chleachdadh a tha 32 pìosan no nas fhaide de dh'fhaid. (airson faid nas motha na 64 pìosan, mar as trice bidh gnìomhan hash criptografach air an cleachdadh).

A dh’ aindeoin gun do sgrìobh mi na bu thràithe gum feum sinn àite a shàbhaladh anns a h-uile dòigh, bidh sinn fhathast a’ cleachdadh checksum 32-bit (chan eil pìosan 16 gu leòr, tha coltachd tubaist nas àirde na 0.01%; agus 24 pìosan, mar a tha iad). ràdh, Nach 'eil aon chuid an so no ann).

Faodaidh gearan èirigh an seo: an do shàbhail sinn a h-uile byte nuair a thagh sinn teannachadh gus a-nis 4 byte a thoirt seachad aig an aon àm? Nach biodh e na b’ fheàrr gun a bhith a’ teannachadh no a’ cur checksum ris? Gu dearbh chan eil, chan eil teannachadh ann chan eil ciall, nach fheum sinn sgrùdadh iomlanachd.

Nuair a bhios sinn a’ taghadh polynomial, cha bhith sinn ag ath-thòiseachadh a’ chuibhle, ach a’ gabhail an CRC-32C a tha mòr-chòrdte a-nis.
Bidh an còd seo a’ lorg mhearachdan 6 bit air pacaidean suas gu 22 bytes (is dòcha a’ chùis as cumanta dhuinne), mearachdan 4 bit air pacaidean suas gu 655 bytes (cuideachd cùis chumanta dhuinn), 2 no àireamh neònach sam bith de mhearachdan air pacaidean de fhad reusanta sam bith.

Ma tha ùidh aig duine anns a’ mhion-fhiosrachadh

artaigil Wikipedia mu dheidhinn CRC.

Paramadairean còd crc-32c air Làrach-lìn Koopman - is dòcha am prìomh eòlaiche CRC air a’ phlanaid.

В an artaigil aige tha còd inntinneach eile, a bheir seachad crìochan beagan nas fheàrr airson na faid pacaid a tha buntainneach dhuinne, ach cha do bheachdaich mi air an eadar-dhealachadh mòr, agus bha mi comasach gu leòr còd àbhaisteach a thaghadh an àite an tè àbhaisteach agus air a dheagh sgrùdadh.

Cuideachd, leis gu bheil an dàta againn air a dhlùthadh, tha a’ cheist ag èirigh: am bu chòir dhuinn àireamhachadh dàta teann no neo-bhrùichte obrachadh a-mach?

Argamaidean airson a bhith a’ tomhas an t-seic de dhàta neo-bhrùichte:

• Feumaidh sinn mu dheireadh sgrùdadh a dhèanamh air sàbhailteachd stòradh dàta - mar sin bidh sinn ga sgrùdadh gu dìreach (aig an aon àm, thèid mearachdan a dh’ fhaodadh a bhith ann an cur an gnìomh teannachadh / dì-dhùmhlachadh, milleadh bho chuimhne briste, msaa);
• Tha buileachadh gu math aibidh aig an algairim deflate ann an zlib agus cha bu chòir tuiteam le dàta cuir a-steach “cam”; a bharrachd air an sin, gu tric bidh e comasach dha mearachdan a lorg gu neo-eisimeileach anns an t-sruth cuir a-steach, a ’lughdachadh an coltachd iomlan gun lorgar mearachd (rinn e deuchainn le bhith a’ tionndadh aon phìos ann an clàr goirid, lorg zlib mearachd ann an timcheall air trian de chùisean).

Argamaidean an aghaidh àireamhachadh an t-seic de dhàta neo-bhrùichte:

• Tha CRC “air a dhealbhadh gu sònraichte” gu sònraichte airson na beagan mhearachdan a tha àbhaisteach do chuimhne flash (faodaidh beagan mearachd ann an sruth teann atharrachadh mòr adhbhrachadh anns an t-sruth toraidh, air an urrainn dhuinn, gu teòiridheach a-mhàin, “bualadh” a ghlacadh);
• Cha toil leam am beachd a bhith a’ toirt seachad dàta a dh’ fhaodadh a bhith briste chun an decompressor, Cò aig tha fiosciamar a bheir e freagairt.

Anns a’ phròiseact seo, chuir mi romham gluasad bhon chleachdadh ris an gabhar san fharsaingeachd a bhith a’ stòradh seic de dhàta neo-bhrùichte.

Geàrr-chunntas: Bidh sinn a’ cleachdadh CRC-32C, bidh sinn a’ tomhas an t-seic bhon dàta anns an fhoirm anns a bheil iad air an sgrìobhadh gu flash (às deidh teannachadh).

Iomallachd

Chan eil cleachdadh còdadh gun fheum, gu dearbh, a’ cur às do chall dàta, ge-tà, faodaidh e gu mòr (gu tric le iomadh òrdugh meudachd) lùghdachadh a dhèanamh air an coltas gun tèid dàta neo-ruigsinneach a chall.

Faodaidh sinn diofar sheòrsaichean call-obrach a chleachdadh gus mearachdan a cheartachadh.
Faodaidh còdan hamming mearachdan aon-phìos a cheartachadh, faodaidh còdan caractar Reed-Solomon, ioma leth-bhreac de dhàta còmhla ri checksums, no còdachadh mar RAID-6 cuideachadh gus dàta fhaighinn air ais eadhon ma thachras coirbeachd mòr.
An toiseach, bha mi dealasach a thaobh cleachdadh farsaing de chòdadh a tha an aghaidh mhearachdan, ach an uairsin thuig mi gum feum sinn an toiseach beachd a bhith againn air dè na mearachdan a tha sinn airson sinn fhèin a dhìon, agus an uairsin tagh còdadh.

Thuirt sinn na bu thràithe gum feumar mearachdan a lorg cho luath ‘s a ghabhas. Dè na h-amannan as urrainn dhuinn a thighinn tarsainn air mearachdan?

1. Clàradh neo-chrìochnaichte (airson adhbhar air choireigin aig àm clàraidh chaidh an cumhachd a chuir dheth, chaidh an sùbh-craoibhe a reothadh, ...)
   Gu mì-fhortanach, ma thachras mearachd mar sin, chan eil air fhàgail ach dearmad a dhèanamh air clàran neo-dhligheach agus beachdachadh air an dàta a chaidh a chall;
2. Sgrìobh mearachdan (airson adhbhar air choireigin, cha b’ e na chaidh a sgrìobhadh chun chuimhne flash na chaidh a sgrìobhadh)
   Is urrainn dhuinn a leithid de mhearachdan a lorg sa bhad ma nì sinn deuchainn air a leughadh dìreach às deidh clàradh;
3. Saobhadh dàta ann an cuimhne aig àm stòraidh;
4. Mearachdan leughaidh
   Gus a cheartachadh, mura h-eil an t-seic a 'freagairt, tha e gu leòr an leughadh ath-aithris grunn thursan.

Is e sin, chan urrainnear ach mearachdan den treas seòrsa (truailleadh dàta gun spionnadh rè stòradh) a cheartachadh às aonais còdadh a tha an aghaidh mearachd. Tha e coltach gu bheil mearachdan mar sin fhathast gu math eu-coltach.

Geàrr-chunntas: chaidh co-dhùnadh còdadh gun fheum a thrèigsinn, ach ma tha gnìomhachd a’ nochdadh mearachd a ’cho-dhùnaidh seo, an uairsin till air ais gu beachdachadh air a’ chùis (le staitistig cruinnichte mu thràth air fàilligidhean, a leigeas le bhith a ’taghadh an seòrsa còdaidh as fheàrr).

Прочее

Gu dearbh, chan eil cruth na h-artaigil a 'toirt cothrom dhuinn a h-uile pìos den chruth a dhìon (agus tha mo neart air ruith a-mach mu thràth), mar sin thèid mi gu h-aithghearr thairis air cuid de phuingean nach deach suathadh roimhe.

• Chaidh co-dhùnadh a h-uile duilleag a dhèanamh “co-ionann”
  Is e sin, cha bhi duilleagan sònraichte ann le meata-dàta, snàithleanan fa leth, msaa, ach an àite sin aon snàithlean a bhios ag ath-sgrìobhadh a h-uile duilleag mu seach.
  Bidh seo a’ dèanamh cinnteach gum bi eadhon caitheamh air na duilleagan, gun aon phuing fàiligeadh, agus is toil leam e;
• Tha e riatanach ullachadh airson dreachdadh den chruth.
  Tha cruth gun àireamh dreach anns a’ bhann-cinn olc!
  Tha e gu leòr raon le àireamh draoidheachd sònraichte (ainm-sgrìobhte) a chuir ri bann-cinn na duilleige, a sheallas an dreach den chruth a chaidh a chleachdadh (Chan eil mi a’ smaoineachadh gum bi eadhon dusan dhiubh ann an cleachdadh);
• Cleachd bann-cinn fad caochlaideach airson clàran (le tòrr dhiubh), a 'feuchainn ri dhèanamh 1 byte fada sa mhòr-chuid de chùisean;
• Gus fad a’ chinn agus fad a’ phàirt trim den chlàr teann a chòdachadh, cleachd còdan binary fad caochlaideach.

Chuidich e gu mòr gineadair air-loidhne Còdan airson Huffman. Ann am beagan mhionaidean bha e comasach dhuinn na còdan faid caochlaideach a bha a dhìth a thaghadh.

Tuairisgeul air cruth stòradh dàta

Òrdugh byte

Tha raointean nas motha na aon byte air an stòradh ann an cruth mòr-endian (òrdugh lìonra byte), is e sin, tha 0x1234 sgrìobhte mar 0x12, 0x34.

Duilleagadh

Tha a h-uile cuimhne flash air a roinn ann an duilleagan den aon mheud.

Is e meud na duilleige àbhaisteach 32Kb, ach chan eil barrachd air 1/4 de mheud iomlan a’ chip cuimhne (airson chip 4MB, gheibhear 128 duilleag).

Bidh gach duilleag a’ stòradh dàta gu neo-eisimeileach bhon fheadhainn eile (is e sin, chan eil dàta air aon duilleag a’ toirt iomradh air dàta air duilleag eile).

Tha na duilleagan uile air an àireamhachadh ann an òrdugh nàdarrach (ann an òrdugh dìreadh nan seòlaidhean), a’ tòiseachadh le àireamh 0 (bidh duilleag neoni a’ tòiseachadh aig seòladh 0, a’ chiad duilleag a’ tòiseachadh aig 32Kb, an dàrna duilleag a’ tòiseachadh aig 64Kb, msaa.)

Tha a’ chip cuimhne air a chleachdadh mar bufair cearcallach (bufair fàinne), is e sin, an toiseach bidh sgrìobhadh a’ dol gu duilleag àireamh 0, an uairsin àireamh 1, ..., nuair a lìonas sinn an duilleag mu dheireadh, bidh cearcall ùr a’ tòiseachadh agus tha clàradh a’ leantainn bho dhuilleag neoni. .

Taobh a-staigh na duilleige

Aig toiseach na duilleige, tha bann-cinn duilleag 4-byte air a stòradh, an uairsin sgrùdadh cinn (CRC-32C), an uairsin tha clàran air an stòradh anns an fhòrmat “header, data, checksum”.

Tha tiotal na duilleige (uaine salach san dealbh) air a dhèanamh suas de:

• raon dà-byte Magic Number (cuideachd na chomharra air an dreach cruth)
  airson an dreach làithreach den chruth tha e air a thomhas mar 0xed00 ⊕ номер страницы;
• cuntair dà-byte “Dreach duilleag” (ath-sgrìobh àireamh cearcall cuimhne).

Tha inntrigidhean air an duilleag air an stòradh ann an cruth teann (tha an algairim deflate air a chleachdadh). Tha a h-uile clàr air aon duilleag air a dhlùthadh ann an aon snàithlean (tha faclair cumanta air a chleachdadh), agus air gach duilleag ùr bidh teannachadh a’ tòiseachadh às ùr. Is e sin, gus clàr sam bith a dhì-dhùmhlachadh, tha feum air a h-uile clàr roimhe bhon duilleag seo (agus dìreach am fear seo).

Bidh gach clàr air a dhlùthadh leis a’ bhratach Z_SYNC_FLUSH, agus aig deireadh an t-srutha dhlùthaichte bidh 4 bytes 0x00, 0x00, 0xff, 0xff, is dòcha aon no dhà a bharrachd neoni bytes ro làimh.
Bidh sinn a’ tilgeadh air falbh an t-sreath seo (4, 5 no 6 bytes fada) nuair a bhios sinn a’ sgrìobhadh gu cuimhne flash.

Is e bann-cinn a’ chlàir 1, 2 no 3 bytes a’ stòradh:

• aon bhìosa (T) a 'sealltainn an seòrsa clàr: 0 - co-theacsa, 1 - log;
• raon de dh'fhaid caochlaideach (S) bho 1 gu 7 pìosan, a 'mìneachadh fad a' chinn agus an "earball" a dh'fheumar a chur ris a 'chlàr airson dì-dhùmhlachadh;
• fad clàr (L).

S clàr luach:

S
Fad cinn, bytes
Air a chuir air falbh air sgrìobhadh, byte

0
1
5 (00 00 00 ff ff)

10
1
6 (00 00 00 00 ff ff)

110
2
4 (00 00 ff ff)

1110
2
5 (00 00 00 ff ff)

11110
2
6 (00 00 00 00 ff ff)

1111100
3
4 (00 00 ff ff)

1111101
3
5 (00 00 00 ff ff)

1111110
3
6 (00 00 00 00 ff ff)

Dh’ fheuch mi ri sealltainn, chan eil fhios agam dè cho soilleir ‘s a thionndaidh e a-mach:

Tha buidhe an seo a’ comharrachadh an raon T, geal an raon S, uaine L (fad an dàta teannachaidh ann am bytes), gorm an dàta teannachaidh, dearg na bytes deireannach den dàta teannachaidh nach eil sgrìobhte gu cuimhne flash.

Mar sin, is urrainn dhuinn cinn-cinn clàran den fhad as cumanta (suas gu 63 + 5 bytes ann an cruth teann) a sgrìobhadh ann an aon byte.

Às deidh gach clàr, thèid seic CRC-32C a stòradh, anns a bheil luach inverted an t-seic roimhe air a chleachdadh mar an luach tùsail (init).

Tha seilbh aig CRC “fad”, tha an fhoirmle a leanas ag obair (a bharrachd air no às aonais tionndadh bit sa phròiseas): .
Is e sin, gu dearbh, bidh sinn ag obrachadh a-mach an CRC de gach bytes de chinn-cinn agus dàta roimhe air an duilleag seo.

Dìreach às deidh an t-seic tha ceann-cinn an ath chlàr.

Tha an bann-cinn air a dhealbhadh ann an dòigh is gum bi a’ chiad byte aige an-còmhnaidh eadar-dhealaichte bho 0x00 agus 0xff (ma choinnicheas sinn ri 0xff an àite a’ chiad byte den cheann-cinn, tha seo a’ ciallachadh gur e raon gun chleachdadh a tha seo; tha 0x00 a’ comharrachadh mearachd).

Algorithms eisimpleir

A ' leughadh bho flash cuimhne

Bidh leughadh sam bith a’ tighinn le seic checksum.
Mura h-eil an t-seic a 'freagairt, thèid an leughadh a-rithist grunn thursan an dòchas an dàta ceart a leughadh.

(tha seo a 'dèanamh ciall, chan eil Linux a' clàradh leughaidhean bho NOR Flash, air a dhearbhadh)

Sgrìobh gu cuimhne flash

Bidh sinn a’ clàradh an dàta.
Leughaidh sinn iad.

Mura h-eil an dàta leughaidh a’ freagairt ris an dàta sgrìobhte, lìonaidh sinn an raon le neamhan agus comharraichidh sinn mearachd.

Ag ullachadh microcircuit ùr airson obrachadh

Airson tòiseachadh, tha bann-cinn le dreach 1 air a sgrìobhadh chun chiad duilleag (no an àite neoni).
Às deidh sin, tha a’ chiad cho-theacsa air a sgrìobhadh chun duilleag seo (anns a bheil UUID an inneil agus na roghainnean bunaiteach).

Sin e, tha an cuimhne flash deiseil airson a chleachdadh.

A 'luchdachadh an inneal

Nuair a thèid an luchdachadh, thèid a’ chiad 8 byte de gach duilleag (cinn-cinn + CRC) a leughadh, thathas a’ toirt aire do dhuilleagan le Àireamh Draoidheachd neo-aithnichte no CRC ceàrr.
Bho na duilleagan “ceart”, tha duilleagan leis an dreach as àirde air an taghadh, agus tha an duilleag leis an àireamh as àirde air a thoirt bhuapa.
Tha a’ chiad chlàr air a leughadh, thathas a’ sgrùdadh ceartachd an CRC agus làthaireachd a’ bhratach “co-theacsa”. Ma tha a h-uile càil ceart gu leòr, thathas den bheachd gu bheil an duilleag seo gnàthach. Mura h-eil, bidh sinn a’ dol air ais chun fhear roimhe gus an lorg sinn duilleag “beò”.
agus air an duilleag a chaidh a lorg leugh sinn na clàran gu lèir, an fheadhainn a bhios sinn a’ cleachdadh leis a’ bhratach “co-theacsa”.
Sàbhail am faclair zlib (bidh feum air airson a chur ris an duilleag seo).

Sin e, tha an luchdachadh sìos deiseil, tha an co-theacsa air ath-nuadhachadh, faodaidh tu obrachadh.

A' cur a-steach iris-latha

Bidh sinn a' teannachadh a' chlàir leis an fhaclair cheart, a' sònrachadh Z_SYNC_FLUSH Chì sinn a bheil an clàr teannaichte a' freagairt air an duilleag làithreach.
Mura h-eil e iomchaidh (no bha mearachdan CRC air an duilleag), tòisich duilleag ùr (faic gu h-ìosal).
Bidh sinn a 'sgrìobhadh sìos an clàr agus CRC. Ma thachras mearachd, tòisich duilleag ùr.

Duilleag ùr

Bidh sinn a’ taghadh duilleag an-asgaidh leis an àireamh as lugha (tha sinn den bheachd gur e duilleag an-asgaidh a th’ ann an duilleag le seic ceàrr anns a’ bhann-cinn no le dreach nas lugha na an tè a th’ ann an-dràsta). Mura h-eil na duilleagan sin ann, tagh an duilleag leis an àireamh as lugha bhon fheadhainn aig a bheil dreach co-ionann ris an fhear a th’ ann an-dràsta.
Sgrios sinn an duilleag taghte. Bidh sinn a’ sgrùdadh na tha ann le 0xff. Ma tha rudeigin ceàrr, gabh an ath dhuilleag an-asgaidh, msaa.
Bidh sinn a’ sgrìobhadh bann-cinn air an duilleag a chaidh a dhubhadh às, is e a’ chiad inntrig staid a’ cho-theacsa mar a tha e an-dràsta, is e an ath rud an inntrigeadh log neo-sgrìobhte (ma tha fear ann).

Co-fhreagarrachd cruth

Nam bheachd-sa, thionndaidh e a-mach gur e cruth math a bh’ ann airson sruthan fiosrachaidh nas motha no nas lugha a stòradh (teacsa shìmplidh, JSON, MessagePack, CBOR, is dòcha protobuf) ann an NOR Flash.

Gu dearbh, tha an cruth “air a dhealbhadh gu sònraichte” airson SLC NOR Flash.

Cha bu chòir a chleachdadh le meadhanan BER àrd leithid NAND no MLC NOR (A bheil a leithid de chuimhne eadhon ri fhaighinn airson a reic? Chan fhaca mi ach iomradh air ann an obraichean air còdan ceartachaidh).

A bharrachd air an sin, cha bu chòir a chleachdadh le innealan aig a bheil an FTL aca fhèin: USB flash, SD, MicroSD, msaa (airson a leithid de chuimhne chruthaich mi cruth le meud duilleag de 512 bytes, ainm-sgrìobhte aig toiseach gach duilleag agus àireamhan clàraidh sònraichte - uaireannan bha e comasach an dàta gu lèir fhaighinn air ais bho dhràibhear flash “glitched” le leughadh sreath sìmplidh).

A rèir nan gnìomhan, faodar an cruth a chleachdadh gun atharrachadh air draibhearan flash bho 128Kbit (16Kb) gu 1Gbit (128MB). Ma thogras tu, faodaidh tu a chleachdadh air sgoltagan nas motha, ach is dòcha gum feum thu meud na duilleige atharrachadh (Ach an seo tha a ’cheist mu ion-dhèantachd eaconamach ag èirigh mar-thà; chan eil a’ phrìs airson meud mòr NOR Flash brosnachail).

Ma tha an cruth inntinneach aig cuideigin agus gu bheil e airson a chleachdadh ann am pròiseact fosgailte, sgrìobh, feuchaidh mi ris an ùine a lorg, snas a chur air a’ chòd agus ga phostadh air github.

co-dhùnadh

Mar a chì thu, aig a 'cheann thall thionndaidh an cruth a-mach gu bhith sìmplidh agus eadhon sgìth.

Tha e duilich a bhith a’ nochdadh mean-fhàs mo bheachd ann an artaigil, ach creid mi: an toiseach bha mi airson rudeigin sòlaimte, do-sheachanta a chruthachadh, comasach air mairsinn eadhon spreadhadh niùclasach faisg air làimh. Ach, bhuannaich adhbhar (tha mi an dòchas) fhathast agus mean air mhean ghluais prìomhachasan a dh’ ionnsaigh sìmplidheachd agus dlùth-chomas.

Am faodadh e bhith gun robh mi ceàrr? Seadh, cinnteach. Is dòcha gu bheil e a’ tionndadh a-mach, mar eisimpleir, gun do cheannaich sinn baidse de microcircuits de chàileachd ìosal. No airson adhbhar air choireigin eile cha bhith an uidheamachd a’ coinneachadh ri dùilean earbsachd.

A bheil plana agam airson seo? Tha mi a’ smaoineachadh às deidh dhut an artaigil a leughadh nach eil teagamh sam bith agad gu bheil plana ann. Agus chan eil eadhon na aonar.

Air nota beagan nas cunnartaiche, chaidh an cruth a leasachadh an dà chuid mar roghainn obrach agus mar “bailiùn deuchainn”.

Aig an àm seo tha a h-uile dad air a 'bhòrd ag obair gu math, gu litearra an latha eile thèid am fuasgladh a chleachdadh (mu thimcheall) air ceudan de dh’ innealan, chì sinn dè thachras ann an gnìomhachd “sabaid” (gu fortanach, tha mi an dòchas gun leig an cruth leat fàilligidhean a lorg gu earbsach; gus an urrainn dhut làn staitistig a chruinneachadh). Ann am beagan mhìosan bidh e comasach co-dhùnaidhean a tharraing (agus ma tha thu mì-shealbhach, eadhon nas tràithe).

Ma lorgar, stèidhichte air toraidhean cleachdaidh, droch dhuilgheadasan agus gu bheil feum air leasachaidhean, bidh mi gu cinnteach a’ sgrìobhadh mu dheidhinn.

Litreachas

Cha robh mi airson liosta fada tedious de dh’ obraichean cleachdte a dhèanamh; às deidh a h-uile càil, tha Google aig a h-uile duine.

An seo chuir mi romhpa liosta de thoraidhean fhàgail a bha coltas gu sònraichte inntinneach dhomh, ach mean air mhean rinn iad imrich gu dìreach a-steach do theacsa an artaigil, agus dh’ fhan aon rud air an liosta:

1. Goireasach infgen bhon ùghdar zlib. Is urrainn dhaibh na tha ann an tasglann deflate/zlib/gzip a thaisbeanadh gu soilleir. Ma dh’ fheumas tu dèiligeadh ri structar a-staigh an cruth deflate (no gzip), tha mi gu mòr ga mholadh.

Source: www.habr.com