Programátorská hádanka 4 - céčkovská zrada

26.8.2010 19:00 | Přečteno: 2187× | poslední úprava: 26.8.2010 22:14

Už dlouho nevyšla žádná programátorská hádanka, tak to musím napravit Dnes bude trochu lehčí než minule. Setkal se s tím určitě každý, kdo alespoň přičuchnul k C nebo C++.
Mám funkci Trim() pro ořezávání bílých znaků ze začátku a z konce textu. Když tedy např. dostane řetězec „ lenochod na pochodu\n“, vrátí „lenochod na pochodu“. Za bílý znak pro jednoduchost považuji znaky jen s ASCII hodnotou menší nebo rovno než mezera (tedy mezeru a řídící znaky). Funkce přímo přepisuje vstupní řetězec; vzhledem k tomu, že se ořezáním řetězec nikdy neprodlouží, může si to dovolit.

Zde je již kód:

void Trim(char *str) {
  int zleva;     //kolik bílých znaků zleva oříznu
  for (zleva = 0; str[zleva] != '\0'; zleva++) {
    if (str[zleva] > ' ') break;
  }

  int i;      //zkopíruju zbytek řetězce
  for (i = 0; str[i+zleva] != '\0'; i++) {
    str[i] = str[i+zleva];
  }
        //najdu konec řetězce
  for (i--; i >= 0 && str[i] <= ' '; i--);

  str[i+1] = '\0';		//a oříznu
}

Celkem krátký kód, poměrně lehký, skoro školní úloha. Nicméně, tato funkce nepracuje správně obsahuje minimálně 2 různé chyby, které způsobují, že existuje vstup, pro který nedává očekávaný výstup.

Najdete je? Ještě dodávám, že kód můžete i debugovat, ačkoli vám to pravděpodobně moc nepomůže.

Domněnky a řešení pište do komentářů. Vy ostatní se při přemýšlení samozřejmě do komentářů nedívejte

Řešení:
Na správné řešení přišel Ondrej 'SanTiago' Zajicek.

První chyba je, že typ char je znaménkový, takže znaky >= 128 (typicky znaky s diakritikou, v libovolném kódování) jsou vlastně záporné. Z tohoto důvodu neprojdou podmínkou if (str[zleva] > ' ') a jdou uřezány společně s bílými znaky. Je to trochu od jazyka C/C++ zrada; sice je znaménkový typ konzistentní se standardní „znaménkovostí“ jiných typů, ale u řetězců toto nemá význam; neumím si představit, kdy bych využil, že ASCII >= 128 je reprezentováno zápornými hodnotami. Naopak je mnoho případů, kdy dochází k chybám a podivným nelogičnostem (viz např. tato ukázka). V Javě jsou třeba všechny typy striktně znaménkové, ale typ char je jediný neznaménkový (16bitový). Taktéž i jiné jazyky nikdy neberou znak jako záporné číslo.

Druhou chybou je použití typu int k indexování. Typ int je 4bajtový (nebo 2bajtový v 16bitovém prostředí) a nehodí se tak pro adresaci paměti. K adresaci paměti je vhodné použít typ size_t (neznaménkový) nebo ptrdiff_t (znaménkový). Tyto typy tak veliké, jak veliký je ukazatel; na 32bitovém mají 4 bajty, na 64bitovým 8 bajtů. V tomto případě by se program v 64bitovém prostředí zacyklil na prvním cyklu při 2 GiB dlouhém řetězci. Na 32bitovém prostředí by pak neořízl řetězec zprava (hned by vyskočil z třetí podmínky).        

Anketa

Komentáře

[vlastikroot]

Sakra! Obě jsem našel, až když jsem zahlasoval, že nevidim ani jednu

[vlastikroot]

Ne, spíš to vypadá, že vidim chyby tam, kde vlastně nejsou.

[Aleš Janda]

Tak napiš, které vidíš

[jas]

Staci NULL a "" alebo sa nad tym treba skutocne zamysliet (a najst este treti vstup)?

[Semo]

NULL nechapem ako vstup, ktory nefunguje. Ako by si definoval trimovanie? A bud blbo vidim alebo "" zbehne ok. Ale napr "   " nezbehne ok - neotrimuje

[Aleš Janda]

Více mezer také otrimuje - ořízne to ten příkaz úplně na konci, protože 'i' tam bude -1.

NULL není platný vstup, takže to na něm zhavaruje (a je to správně) - to neberu jako chybu.

[Semo]

Ha, vravel som ze blbo vidim, nevsimol som si ";" na konci 2. for cyklu.

[maddoxik]

Nejsem programator, ale tipnul bych, ze se nekontroluji meze, takze v pripade hooooooodne dlouheho retezce pretece promenna zleva a pak dohavaruje ten druhy cyklus, protoze index i bude zaporny.

[Aleš Janda]

Jsi blízko jedné z chyb

[Let_Me_Be]

Ono by to chtelo definovat co je validni vstup.

[Let_Me_Be]

A taky jestli to ma delat to co je napsano v zadani, nebo opravdu Trim.

[Aleš Janda]

Validní vstup je jakýkoli řetězec typu char*, neNULLová hodnota, ukončená '\0'. Může být i prázdný.

Ořezávají se všechny řídící znaky ASCII < 32 a mezera. Myslel jsem, že je to standardní chování trimu, teď vidím, že např. PHP standardně ořezává jen některé řídící znaky, ale to je víceméně jen detail.

[Let_Me_Be]

No, ono totiz < 32 je neco jineho nez 0..32

[sivlk]

Ako mam hlasovat ked som nasiel 3 chyby?

[Aleš Janda]

Jaké?

[Ondrej 'SanTiago' Zajicek]

1) Indexuje mimo meze na vstupu slozenym ze samych mezer.

2) trimuje i znaky s nahozenym nejvyssim bitem, protoze char je obvykle interpretovan jako signed.

3) Na 64bit Linuxu se zacykli se na stringu delsim nez 4 GB :–)

[Aleš Janda]

1) Indexuje mimo meze na vstupu slozenym ze samych mezer.

Proč myslíte? V kterém cyklu?

2) trimuje i znaky s nahozenym nejvyssim bitem, protoze char je obvykle interpretovan jako signed.

Gratuluji, toto je ta první chyba

3) Na 64bit Linuxu se zacykli se na stringu delsim nez 4 GB :–)

A gratuluji znova, toto je ta druhá chyba konkrétně se zacyklí i na stringu delším než 2 GiB, a tedy i na 32bit

[Ondrej 'SanTiago' Zajicek]

konkrétně se zacyklí i na stringu delším než 2 GiB, a tedy i na 32bit

Opravdu se rozbije i na 32bit systemu? Nejsem si teda presne jist, jak se chova pointerova arimetrika pri preteceni, ale tipoval bych ze to vezme modulo 2^32, takze se to bude prakticky chovat jako by byl index unsigned.

[Ondrej 'SanTiago' Zajicek]

V takovem pripade by se na 32bit systemu na souboru vetsim nez 2 GB chovala spatne az treti smycka (skoncila by ihned), coz je trochu jiny pripad nez na 64bit systemu (indexace mimo meze v prvni smycce), takze to lze klasifikovat jako dve ruzne chyby. ;–)

[Aleš Janda]

Máte pravdu, po větším zamyšlení vlastně je to přesně tak - na 32bitech by to vlastně „náhodou“ fungovalo, ale rozbilo se to až dál. Zajímavé, jak je to vlastně zmatečné.

Každopádně jste přišel na obě chyby, gratuluju

[mich]

Nejspíš je to hodně hloupá otázka, ale přesto jí položím. Jak alokujete místo pro retezec vetsi nez maximalni hodnota size_t (=int)?

[Aleš Janda]

Int je znaménkový, čili max. kladný index je 2^31. Funkce malloc přitom bere size_t, což je neznaménkový, čili 2^32 (na 64bit 2^64). Neplatí tedy, že int = size_t; myslím, že bych alokovat 3 GB klidně mohl.

[Ondrej 'SanTiago' Zajicek]

Tak u 1) jsem se taky nechal nachytat, tohle zrejme funguje.

Upresneni k 3) - vzhledem k signed indexu to selze uz na 2 GB stringu indexovanim mimo meze.

[Let_Me_Be]

str[i+1] = '\0'; je out of bounds pro prazdny retezec a taky to nefunguje pro retezce ktere jsou jenom z bilych znaku

Netusim jestli to je jedna nebo jsou to dve chyby.

[Let_Me_Be]

Hmm, tak jsem se nechal nachytat.

[Jarda]

void Trim(char **str)?

[Jarda]

Ale nic, zacatek se nemeni.

[R]

Nielen, ze je to zle, ale este to je aj neefektivne - kopiruje sa kus retazca, ktory sa hned potom zahodi.

[Filip Jirsák]

Okopírovat se to dá taky efektivněji než to posouvat bajt po bajtu.

[Kvakor]

Ano, je neefektivní kopírovat řetězec, který ještě není ořizlý zprava, stačilo by prvně provést oříznutí z obou stran a pak teprve kopírovat. Případně to celé nacpat do jednoho jediného cyklu, aby se zbytečně nezaplácávala cache.

[R]

Tu je najmenej jedna chyba:

void trim(char *str) {
  char *begin = str, *end;

  while ((unsigned char)*begin <= ' ' && *begin != '\0')
    begin++;

  end = begin + strlen(begin);
  while ((unsigned char)*end <= ' ' && end > begin)
    end--;

  memmove(str, begin, end - begin + 1);
  str[end - begin + 1] = '\0';
}

[Aleš Janda]

Tak trochu mi to dalo zabrat ale pokud má předaný buffer jen jeden bajt (a tam je koncová nula, čili prázdný řetězec, pak begin = end = str a tudíž poslední řádek zapíše 0 na index 1 => za buffer.

[__dark__]

Ty chyby jsou zřejmé, ale teď je třeba se trochu zamyslet. Nepoužívá náhodou i Qt/Java/.NET typ int pro velikost a indexaci datových struktur? Možná tu máme omezení do budoucna

[zulu]

Správně jsi napsal indexaci, zatímco autor píše o adresaci. K adresaci se int opravdu nehod, ale k indexaci náramně.

[kolcon]

Zlaty Perl a jednoduche reseni regexpem...

[Michal Kubeček]

Přiznávám se bez mučení, že úvahu "považujme za bílý znak cokoli s kódem menším nebo rovným 32" jsem bral za natolik nesmyslnou, že jsem si prostě místo toho testu v duchu dosadil isspace() a chybu tudíž neodhalil, protože mne nenapadlo hledat chyták v podobě chybné implementace něčeho, co je samo o sobě chyba.

Mimochodem, určitě je podle normy char znaménkový? Vždycky jsem měl za to, že je na implementaci, jestli bude char totéž co signed char nebo unsigned char, a programátor by tudíž neměl předpokládat ani jedno.

[Karel Zak]

Mimochodem, určitě je podle normy char znaménkový? Vždycky jsem měl za to, že je na implementaci, jestli bude char totéž co signed char nebo unsigned char, a programátor by tudíž neměl předpokládat ani jedno.

C99 6.2.5 Types

An object declared as type char is large enough to store any member of the basic execution character set. If a member of the *basic execution character set* is stored in a char object, its value is guaranteed to be nonnegative. If any *other character* is stored in a char object, the resulting value is *implementation-defined* but shall be within the range of values that can be represented in that type.

5.2.1 Character sets

Both the basic source and basic execution character sets shall have the following members: the 26 uppercase letters of the Latin alphabet, the 26 lowercase letters of the Latin alphabet, the 10 decimal digits, 29 graphic characters (pozn. zavorky, carky apod.)

.. tedy zakladni znaky lze predpokladat jako signed, ale vse ostatni je implementation-defined.

Dulezite je, ze to chovani je arch dependent, treba x86 GNU/Linux je signed, ale ARM je unsigned apod. Viz:

http://www.network-theory.co.uk/docs/gccintro/gccintro_71.html

Takze je vhodne bud kompilovat s -fsigned-char pokud trvate na tom, ze char ma nejake urcite znaminko. Jinak v kodu je vhodne pouzivat "char" jen tam kde se nepracuje se znaky, jinak striktne "unsigned char".

[Aleš Janda]

Joj, tak tohle je tedy opravdu zajímavé. O gcc přepínačích na znaménkovost jsem věděl, ale že je to na ARMu defaultně unsigned, to je pro mě novinka. Díky

[R]

Skus si dat retazce ako unsigned char * a pouzivat funkcie ako strlen() - kolko tam budes mat warningov...

[Jardík]

Se dá vždycky přetypovat

[Martin Mareš]

jsem si prostě místo toho testu v duchu dosadil isspace() a chybu tudíž neodhalil

Pozor, s isspace() vznikne velice podobná chyba – není ho totiž dovoleno volat se záporným argumentem.

Vždycky jsem měl za to, že je na implementaci, jestli bude char totéž co signed char nebo unsigned char, a programátor by tudíž neměl předpokládat ani jedno.

Přesně tak.

[rastos]

Nedávno som stretol tiež takú hlúpu chybu. V jave som potreboval nájsť v reťazci A podreťazec B a podľa jeho pozície rozdeliť A na na časť, pred výskytom B, časť zhodnú s B a časť za výskytom B. Case insensitive. A práve tá case-insenstitivta bola riešená prevodom oboch stringov cez toUpper(). Fungovalo to fajn, až kým A neobsahovalo nemecké ostré "ß". To pri prevode cez String.toUpper() vyrobilo "SS" - čím A malo zrazu o jeden znak navyše a zrátané indexy boli tým pádom o jedna posunuté Vyriešené to bolo nakoniec cez regexp.

[Jardík]

Ze ß to vyrobilo SS? Jako z jednoho znaku dva? Nebo to vyrobilo z 1 charu (ve smyslu datového typu) chary 2 (to SS nějaký "spojený znak")? Protože java používá ke kódování řetězců UTF-16, bylo by to naprosto v pořádku a je třeba s tím počítat. Nesnáším algoritmy, co si myslí co jeden char (jako datový typ), to jeden znak.

[rastos]

"straße".length() vrátilo 6 ale "straße".toUpper().length() vrátilo 7, pretože "straße".toUpper() je "STRASSE" a to je 7 znakov.

[Martin Mareš]

Ze ß to vyrobilo SS? Jako z jednoho znaku dva?

Pokud ano, tak to jednalo zcela podle standardu: UniCode (alespoň ve verzi 5.0, do které zrovna koukám) ve svých case mappings opravdu definuje, že 00DF (German es-zed) má jako upper case 0053 0053 (SS). A stejně se, tuším, chová i německý pravopis.

[Jardík]

A jsou to opravdu 2 znaky, nebo je to surrogate pair? Já to unicode nestuduji, ale pokud v řetězci takový znak je, tak String.length nevrátí počet znaků ve smyslu opravdových znaků, ale ve smyslu počtu prvků typu char.
Teď vidím, že to surrogate pair není a že to jsou opravdu jen 2 písmena S - s takovou věcí jsem se ještě nesetkal, každopádně není dobré se spoléhat na String.length, pokud chci počet znaků.

[Martin Mareš]

On by si předně každý, kdo chce měřit délku unicodových řetězců, měl opravdu pořádně rozmyslet, co vlastně chce:

• počet jednotek reprezentace (v UTF-8 nebo UTF-16)
• počet codepointů
• počet znaků (liší se v případě použití kombinujících znaků)