Rejtvenyrovatunk

Ez mi a fax? Avagy WTF?


Pad() {
  local L=${#1}
  local LMod4=$(expr $L % 4)
  if [ $LMod4 -eq 0 ]; then
    Pad=''
  else
    Pad=$(echo '===' | cut -b-$(expr 4 - $LMod4 ))
  fi
  echo "$Pad"
}

Stringekhez készít a hosszuk 4-gyel való oszthatóságához paddingot egyenlőségjelekből. Megadod, hogy milyen hosszú a stringed és annyi egyenlőségjelet köp ki, amennyit ha hozzácsapsz, a hossza 4-gyel osztható lesz. Talán valamelyik base encoding-hoz segédfüggvény, de nem base64-hez, mert ott a padding max. két karakter lehet.

Oldschool Computer - http://oscomp.hu

Jo, es lattal mar base64 encode-olt string vegen 3 darab egyenlosegjelet?

pi@raspberrypi:~$ echo -n "ABC"|base64
QUJD
pi@raspberrypi:~$ echo -n "ABCD"|base64
QUJDRA==
pi@raspberrypi:~$ echo -n "ABCDE"|base64
QUJDREU=
pi@raspberrypi:~$ echo -n "ABCDEF"|base64
QUJDREVG
pi@raspberrypi:~$ echo -n "ABCDEFG"|base64
QUJDREVGRw==
pi@raspberrypi:~$ echo -n "ABCDEFGH"|base64
QUJDREVGR0g=
pi@raspberrypi:~$ echo -n "ABCDEFGHI"|base64
QUJDREVGR0hJ

Nekem ugy tunik, hogy amikor 4-gyel oszthatobol tulcsordul, ott a kovetkezo byte-bol 6 bit megy egy karakterre, 2 bit a kovetkezobe, es == (2 karakter) lesz a padding.

A strange game. The only winning move is not to play. How about a nice game of chess?

Igazságod van, meg lehetne spórolni egy darab egyenlőségjelet, ezzel jelentős gyorsulást és helymegtakarítást érünk el.

-    Pad=$(echo '===' | cut -b-$(expr 4 - $LMod4 ))
+    Pad=$(echo '==' | cut -b-$(expr 4 - $LMod4 ))

Bár szerintem ilyenkor korrekt lenne mögé írni kommentben, hogy valid base64 esetben LMod4 nem lehet 1, ezért volt lehetőség '====' helyett '==='-t írni. Sajnos ezzel agyon is csaptuk az optimalizációt.

Igaz, igaz, pontatlanul fogalmaztam. Újabb próba: A 'töltelékes base64' N*4 bájt hosszú, amiből vissza lehet állítani az eredeti N*3 / N*3-1 / N*3-2 bájt hosszú adatot.
 

Szóval ott tartottunk, hogy egyenlőségjelekkel kell N*4 hosszúra kiegészíteni a 'töltetlen base64-et' hogy a base64 -d ne panaszoljon. (Nem találtam olyan opciót, hogy ne panaszoljon, de olyat sem, hogy base64url szerint működjön.)

Most jön a kollégák jogos meglátása: a 'töltetlen base64' nettó hossza csak N*4,N*4+2,N*4+3 lehet, de N*4+1 nem, tehát az egyenlőségjelek száma is 0, 1 vagy 2 lehet (de 3 nem), és ez alkalmat ad egy bájt megspórolására.

Bár, ahogy már mondtam, az emberi olvasók kedvéért ezt illő odaírni kommentben, amivel sajnos bőven ellensúlyozzuk az egyébként jelentős megtakarítást.

Jó, most esik le, hogy ez az elkódolt hossz és nem fordítva... >_<
Amire én gondoltam, hogy az elkódolt string végére annyi padding karakter kerül be, amennyi az elkódolatlan string hosszából hiányzott a hárommal való maradék nélküli osztáshoz.

Oldschool Computer - http://oscomp.hu

( locsemege v | 2021. 12. 17., p – 00:39 )

A ${parameter:offset} és ${parameter:offset:length} Bash-only dolog? Mert ezzel sokkal kézenfekvőbb.

tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE

( BaT | 2021. 12. 17., p – 12:23 )

Használhat nem shell parancsokat? Mert akkor tudok rá egy egysoros megoldást (ha a bemenetben nincs null karakter):

Pad() {
  echo -n "$1" | dd bs=4 conv=sync 2>/dev/null | tr '\0' '='
}

Teszt:

for source in t te tes test testi testin testing; do
  input=$(echo -n $source | base64 | tr -d '=')
  output=$(Pad $input)
  echo "$source -> $input -> $output -> $(echo -n $output | base64 -d)"
done

t -> dA -> dA== -> t
te -> dGU -> dGU= -> te
tes -> dGVz -> dGVz -> tes
test -> dGVzdA -> dGVzdA== -> test
testi -> dGVzdGk -> dGVzdGk= -> testi
testin -> dGVzdGlu -> dGVzdGlu -> testin
testing -> dGVzdGluZw -> dGVzdGluZw== -> testing

Egyrészt nem tudjuk, hogy a dd ezt hogy oldja meg belül, én azt gondolnám, hogy amennyire lehet optimalizálva van. Másrészt use-case függő, hogy ez mekkora probléma. Milyen gyakran van a Pad függvény meghívva, mekkora a tipikus input, stb.

Premature optimization is the root of all evil.

Benchmarkoljuk ki. Először is generáljunk egy tesztfájlt.

rm -f file.txt && for i in `seq 0 8191`; do head -c 512 /dev/urandom | tr -dc 'a-zA-Z0-9_-' >> file.txt; echo >> file.txt; done

(A generált fájl referenciaként letölthető innen: http://oscomp.hu/depot/file.txt)
Írjunk két tesztszkriptet, ami soronként feldolgozza. Először a dd/tr párost nézzük:

#!/bin/sh

Pad() {
  echo -n "$1" | dd bs=4 conv=sync 2>/dev/null | tr '\0' '='
}

while IFS= read -r line; do
	Pad "$line"
done < file.txt

Teszteljük le mennyit megy:

time ./tesztddtr.sh > /dev/null

real    0m10,931s
user    0m0,368s
sys     0m3,160s

Nézzük most meg a másikat. Annyit változtattam rajta, hogy mivel a maradékszámítást és a cut sebességét akartuk összemérni a másikkal, így a felesleges külső expr meghívásokat Zahy javaslata alapján kitakarítottam belőle.

#!/bin/sh

Pad() {
  local LMod4=$(( ${#1} % 4 ))
  if [ $LMod4 -eq 0 ]; then
    Pad=''
  else
    Pad=$(echo '===' | cut -b-$(( 4 - $LMod4 )))
  fi
  echo "$Pad"
}

while IFS= read -r line; do
	Pad "$line"
done < file.txt

Teszteljük le ezt is:

time ./tesztcut.sh > /dev/null

real    0m9,868s
user    0m0,496s
sys     0m1,680s

The only existing evil are people who declare things evil.

Oldschool Computer - http://oscomp.hu

Tehát a különbség 10% körül van, ami bár nem elhanyagolható, véleményem szerint nagyon ritkán számít.

Illetve még annyit tennék hozzá, hogy a két Pad függvény valójában nem ugyanaz, az én megoldásom hozzáfűzi a paddingot az eredeti stringhez (mivel feltételezem, hogy a padding így van használva). Ezért a második script jóval kevesebb adatot hány a kimenetre, ami befolyásolhatja, meddig fut.

Egy szóval nem mondtam, hogy kardinális különbség van a kettő között, csak azt, hogy nagyobb az overheadje.

Ebben a szcenárióban marginális különbséget jelent maga az outputra küldött pár extra kB, lévén az output át volt irányítva a /dev/null-ra, így kernel szinten történt meg az eldobása; ha kiiratom, akkor a konzolra való firkálás valóban több pluszt csinált volna, de így nem. (Igen, 10 GLoT-nyi adatnál már így is lesz impactja.) Ami viszont fontosabb, hogy azt tkp. senki nem kérte, hogy fűzd hozzá; az eredeti függvény csak a paddingot állította elő, így erősen valószínű, hogy a felhasználása is úgy történik meg, hogy van az encode-olt adat és ahhoz fűzi hozzá a paddingot, amit ez a függvény ad vissza és nem pedig felülírja vele. Nyilván nem kunszt átírni azt az egy sort, de így egyrészt törted a kompatibilitást, másrészt meg az extra adat okozta plusz terhelést is magadnak csináltad.

A legjobb megoldás az, amit Zahy javasolt, mert úgy zéró külső parancs kell neki.

#!/bin/sh

Pad() {
	local LMod4=$(( ${#1} % 4 ))
	case $LMod4 in
		0) Pad='' ;;
		1) Pad='===' ;;
		2) Pad='==' ;;
		3) Pad='=' ;;
	esac
	echo "$Pad"
}

while IFS= read -r line; do
	Pad "$line"
done < file.txt
time ./tesztcase.sh > /dev/null

real    0m0,464s
user    0m0,124s
sys     0m0,336s

Szinte zéró idő a másik kettőhöz képest, magáért beszél.

Oldschool Computer - http://oscomp.hu

de így egyrészt törted a kompatibilitást

Ez csak akkor igaz, ha ez a függvény más scriptekből van hívva, amik nem módosíthatóak. Ha ez egy script privát függvénye, akkor gond nélkül át lehet írni a hívást is, nem fog problémát okozni. A refaktorálás a fejlesztés része, nem kell, sőt, nem is szabad a korábbi hibás döntésekhez ragaszkodni, ha ez nem okoz technikai problémát.

másrészt meg az extra adat okozta plusz terhelést is magadnak csináltad

Mivel nem látjuk, hogyan van a függvény használva, így ez elvileg lehetséges. A gyakorlatban jó eséllyel az input string végére van fűzve, tehát a végeredmény ugyanaz.

Ez csak akkor igaz, ha ez a függvény más scriptekből van hívva, amik nem módosíthatóak.

Nem, a kompatibilitást mindenképpen törted, hiszen módosítás nélkül már nem alkalmazható a függvény. Értsd: ez nem egy drop-in replacement. Az más kérdés, hogy ha a meghívó módosítható, akkor illeszthető, ergo javítható.

A refaktorálás a fejlesztés része, nem kell, sőt, nem is szabad a korábbi hibás döntésekhez ragaszkodni, ha ez nem okoz technikai problémát.

Én is leírtam, hogy "nyilván nem kunszt átírni azt az egy sort" (ezzel kezdtem).

A gyakorlatban jó eséllyel az input string végére van fűzve, tehát a végeredmény ugyanaz.

Mármint módosítás után ugyanaz; jelen pillanatban elég nagy valószínűséggel így a végeredmény úgy fog kinézni, hogy string + string + padding, hiszen nem egy paddingot ad vissza, hanem a stringet és a paddingot.

De igazából meddő a vita, mert Zahy megoldása a legjobb úgyis, az meg ugyanazt adja vissza végeredménynek, amit az eredeti is.

Oldschool Computer - http://oscomp.hu

Így-is úgy-is módosítani kell a forrásfájlt az implementáció megváltoztatásához, ez innentől nem nevezhető drop-in replacementnek, ezért nincs értelme kompatibilitásról beszélni.  Egy ilyen változtatáshoz nálam hozzá tartozik a hívási helyek módosítása is, az egész egy commitot/egy pull requestet/egy patch-et eredményezne, vagyis nem választható ketté a függvény módosítása a hívási helyek módosításával. Mivel ez (feltételezhetően) nem egy publikus függvény, így ez teljesen lényegtelen, akár át is nevezhetném, megváltoztathatnám a paraméterezését, stb., amíg azt egy változtatáson belül teszem, nem fogja törni a kompatibilitást.

Nyilván mivel csak egy script töredéket látunk, így csak feltételezhetem, hogyan van hívva, így nem is adhatok implementációt a hívási helyek módosítására. Ezt, ha igény van a függvény cseréjére, annak kell megtennie, aki ezt a módosítást elvégzi. De ettől még nem tartom a megoldásom rosszabbnak.

Zahy megoldása sem rossz, de az már szubjektív, hogy ki melyik megoldást tartja a legjobbnak. Én mindkét megoldást elfogadnám egy code reviewn, ha nincs nem-funkcionális megkötés arra, hogy mennyire kell hatékonynak lennie.

Így-is úgy-is módosítani kell a forrásfájlt az implementáció megváltoztatásához, ez innentől nem nevezhető drop-in replacementnek, ezért nincs értelme kompatibilitásról beszélni.

Hogyne volna. A hívó szempontjából nem drop-in replacement és a hívót jelen pillanatban nem látjuk.

Egy ilyen változtatáshoz nálam hozzá tartozik a hívási helyek módosítása is, az egész egy commitot/egy pull requestet/egy patch-et eredményezne, vagyis nem választható ketté a függvény módosítása a hívási helyek módosításával.

És ha a hívó egy másik scriptben van? Amit rossz esetben valami bináris generál?

Mivel ez (feltételezhetően) nem egy publikus függvény, így ez teljesen lényegtelen, akár át is nevezhetném, megváltoztathatnám a paraméterezését, stb., amíg azt egy változtatáson belül teszem, nem fogja törni a kompatibilitást.

De, a hívó számára. Értelemszerűen, ha a hívót át lehet írni, akkor nem probléma, de ha nem?

Nyilván mivel csak egy script töredéket látunk, így csak feltételezhetem, hogyan van hívva, így nem is adhatok implementációt a hívási helyek módosítására. Ezt, ha igény van a függvény cseréjére, annak kell megtennie, aki ezt a módosítást elvégzi. De ettől még nem tartom a megoldásom rosszabbnak.

Hát a paddingot megcsinálta, de:
- Kb. 10%-kal lassabb is lett.
- Egy külső tool helyett kettőtől függ.
- Módosítani kell hozzá a hívót is.

Zahy megoldása sem rossz, de az már szubjektív, hogy ki melyik megoldást tartja a legjobbnak.

Tehát szerinted az szubjektív, hogy az övé kis híján 25x gyorsabb a tiednél, nem függ semmilyen külső tool-tól és még a kompatibilitást is megtartotta?

Oldschool Computer - http://oscomp.hu

Hogyne volna. A hívó szempontjából nem drop-in replacement és a hívót jelen pillanatban nem látjuk.

És ha a hívó egy másik scriptben van? Amit rossz esetben valami bináris generál?

De, a hívó számára. Értelemszerűen, ha a hívót át lehet írni, akkor nem probléma, de ha nem?

Ahogy már korábban jeleztem, ha a Pad függvény publikus, abban az esetben természetesen nem lehet szabadon módosítani. De a kapott információ alapján feltételezem, hogy nem ez a helyzet.

- Kb. 10%-kal lassabb is lett.

Konkrét use-case ismerete nélkül nem tudhatjuk, hogy ennek van-e jelentősége. Pl. ha a base64 kódolt string egy hálózati hívás eredménye, vagy a dekódolt string egy hálózati hívás bemenete, továbbá legfeljebb néhány KB-nyi adattal kell foglalkozni egyszerre, akkor jó eséllyel a hálózati hívás latencyje nagyobb lesz, mint ameddig a függvény fut.

Egyébként talán lehet a megoldáson még optimalizálni, tehát ha ez számít, bele lehet fektetni az energiát.

- Egy külső tool helyett kettőtől függ.

UNIX specifikáció szerint mindkettő kötelező, nagyon különleges környezetnek kell lennie, ahol shell scriptet lehet futtatni, de ezek valamelyike nem érhető el. Ez olyan, mintha egy standard (értsd: nem embedded) C projectben külső függőségként tekintenél a standard C függvénykönyvtárra.

- Módosítani kell hozzá a hívót is.

Ezt már kifejtettem, csak akkor probléma, ha a Pad függvény publikus.

Tehát szerinted az szubjektív, hogy az övé kis híján 25x gyorsabb a tiednél, nem függ semmilyen külső tool-tól és még a kompatibilitást is megtartotta?

Ha ez a három szempont nem jelentős az adott use-case esetén, ahogy azt fent kifejtettem bővebben, akkor igen, szubjektív. Más szempontok általában sokkal fontosabbak, pl. érthetőség, karbantarthatóság, portabilitás. Nem állítom, hogy Zahy megoldása ebből a szempontból rosszabb lenne, sőt, érthetőségben szerintem jobb is. De karbantarthatóság szempontjából rosszabb, pl. ha paraméterezhetővé kellene tenni a hosszt, az nem tehető meg egyszerűen.

Ahogy már korábban jeleztem, ha a Pad függvény publikus, abban az esetben természetesen nem lehet szabadon módosítani. De a kapott információ alapján feltételezem, hogy nem ez a helyzet.

Egy feltételezés alapján meghozni egy döntést nem biztos, hogy jó ötlet.

Konkrét use-case ismerete nélkül nem tudhatjuk, hogy ennek van-e jelentősége. Pl. ha a base64 kódolt string egy hálózati hívás eredménye, vagy a dekódolt string egy hálózati hívás bemenete, továbbá legfeljebb néhány KB-nyi adattal kell foglalkozni egyszerre, akkor jó eséllyel a hálózati hívás latencyje nagyobb lesz, mint ameddig a függvény fut.

És ha az egész rendszer egy netbootos hálózati meghajtón van, akkor pusztán a meghívásuk is újabb hálózat-okozta latency-t fog eredményezni.

UNIX specifikáció szerint mindkettő kötelező, nagyon különleges környezetnek kell lennie, ahol shell scriptet lehet futtatni, de ezek valamelyike nem érhető el. Ez olyan, mintha egy standard (értsd: nem embedded) C projectben külső függőségként tekintenél a standard C függvénykönyvtárra.

Egyrészt nem kell nagyon különlegesnek lennie, elég, ha nem UNIX. A POSIX-like shellek maguk sok platformon elérhetőek, de nem biztos, hogy a toolok is. Egy csupasz bash-t szinte bárhová felhányhatsz - akár windowsra is - de a toolok vagy elérhetőek, vagy nem és ha elérhetőek is, akkor is lehet, hogy külön kell őket felrakni, pl. a MinGW-ben is van bash.exe, de a POSIX CLI toolokat külön kell feltenni az MSYS-szel és az is csak egy részüket tartalmazza; mondjuk azt nem tudom, hogy a dd és a tr speciel benne van-e. Másrészt meg ld. az előző bekezdést: a külső függőség nem csak akkor okozhat gondot, ha nem elérhető, hanem akkor is, ha elérhető, de megkötésekkel, pl. a példámban a network drive.

Ezt már kifejtettem, csak akkor probléma, ha a Pad függvény publikus.

Én meg válaszoltam rá: feltételezések alapján nem célszerű kompatibilitást törni.

Ha ez a három szempont nem jelentős az adott use-case esetén, ahogy azt fent kifejtettem bővebben, akkor igen, szubjektív.

A legjobb megoldásra mindig célszerű törekedni, akkor is, ha egy adott use-case alatt nem jön ki valaminek a hátránya, ugyanis ez a kitétel, hogy "ha ez a három szempont nem jelentős", ez már megint egy feltételezésen alapszik. Igen, ha ezek nem fontosak, akkor valóban mindegy. De ha azok, akkor nem. Az övé minden esetben működni fog és sokkal gyorsabban fog működni. (Egy netbootos windowson is.)

portabilitás

Az a külső függőségek növekedésével éppenhogy csökken.

De karbantarthatóság szempontjából rosszabb, pl. ha paraméterezhetővé kellene tenni a hosszt, az nem tehető meg egyszerűen.

Őszintén megvallom, ezt nem értem. Mit értesz a "hossz paraméterezhetőségén"? Azt, hogy nem a stringet adom át a függvénynek paraméterként, hanem a hosszt? Ahhoz csak a ${#1} részt kell sima $1-re cserélni.

Oldschool Computer - http://oscomp.hu

Ha csak belső parancsot akarunk, akkor simán lehet egy case esac. Persze ez sokkal rondább.

Pad() {

local LMod4=$(( ${#1} % 4 ))

case $LMod4 in

0) Pad='' ;;

1) Pad='=' ;;

2) Pad='==' ;;

3) Pad='===' ;;

esac

echo "$Pad"

}

Szívem szerint ? : operátorral csinálnám meg, de abba belehülyül mind a bash, mind a ksh93. (Aritmetikai környezetben - (( azaz )) , vagy $(( forma )) esetén illetve a let "parancs" használatakor - a shell "$x"-nek tekinti a szimpla "x" hivatkozást, azaz változóhivatkozásnak fordítja, és nem sikerült a \, " és ' karakterek olyan kombinációját megadni, amitől érti a dolgot. Azaz kell egy extra változó, amibe ha beteszem a === sringet, no akkor elhalálozik.)

$ x=987654321 $ a=$(( ( 0 == 1 ) ? ${x#?} : ${x#??} )) ; echo $a
7654321
$ a=$(( ( 1 == 1 ) ? ${x#?} : ${x#??} )) ; echo $a
87654321

$ x='===' $ a=$(( ( 0 == 1 ) ? ${x#?} : ${x#??} )) ; echo $a
ksh:  ( 0 == 1 ) ? == : = : arithmetic syntax error
$ a=$(( ( 0 == 1 ) ? ${x#?} : ${x#??} )) ; echo $a
ksh:  ( 0 == 1 ) ? == : = : arithmetic syntax error

tl;dr
Egy-két mondatban leírnátok, hogy lehet ellopni egy bitcoin-t?

Anélkül, hogy konkrétan végiggondoltam volna, a stringből honnan hány karakter esetében nem kell a harmadik paraméterben kivonás, ha a második paraméterben azt mondjuk meg, hogy honnan, a harmadik paramétert elhagyjuk, egyenlőségjelből meg annyi van, hogy a végéig épp a megfelelő darabszámú lesz belőle.

tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE