Pertanyaan C implementasi strcmp menggunakan pengurangan karakter


Saya melihat implementasi ini strcmp beberapa waktu lalu, dan saya punya pertanyaan untuk tujuan murni pendidikan. Mengapa perlu mengonversi input menjadi bilangan bulat 16bit, melakukan matematika dan kemudian mengkonversikan kembali ke 8bit? Apa yang salah dengan melakukan pengurangan dalam 8bit?

int8_t strcmp (const uint8_t* s1, const uint8_t* s2)
{
  while ( *s1 && (*s1 == *s2) )
  {
    s1++; 
    s2++;
  }

  return (int8_t)( (int16_t)*s1 - (int16_t)*s2 );
}

Catatan: kode mengasumsikan 16 bit int mengetik.

EDIT: Disebutkan bahwa C melakukan konversi ke int (misalkan 32bit) secara default. Apakah itu kasus bahkan ketika kode secara eksplisit menyatakan untuk membuang ke 16bit int ?


32
2018-01-18 16:08


asal


Jawaban:


Itu strcmp (a, b) fungsi diharapkan untuk kembali

  • <0 jika string a < string b
  • >0 jika string a > string b
  • 0 jika string a == string b

Tes sebenarnya dibuat pada char pertama yang berbeda dalam dua string di lokasi yang sama (0, terminator string, bekerja juga).

Di sini karena fungsi membutuhkan dua uint8_t (unsigned char), pengembang mungkin khawatir tentang melakukan perbandingan pada dua karakter yang tidak diberi tanda akan memberikan angka antara 0 dan 255, maka nilai negatif tidak akan pernah dikembalikan. Contohnya, 118 - 236 akan kembali -118, tetapi pada 8 bit itu akan kembali 138.

Jadi programmer memutuskan untuk melakukan cast to int_16, bertanda integer (16 bit).

Itu bisa berhasil, dan diberi nilai negatif / positif yang benar (asalkan fungsi kembali int_16 dari pada int_8).

(* Sunting: komentar dari @zwol di bawah ini, promosi bilangan bulat tidak dapat dihindari, jadi ini int16_t casting tidak diperlukan)

Namun final int_8 cor melanggar logika. Karena nilai yang dikembalikan mungkin berasal -255 untuk 255, beberapa nilai ini akan melihat tanda mereka terbalik setelah pemeran int_8.

Misalnya, lakukan 255 - 0 memberi yang positif 255 (pada 16 bit, semua lebih rendah 8 bit ke 1, MSB ke 0) tetapi di int_8 dunia (int int 8 bit) ini negatif, -1, karena kita hanya memiliki 8 bit terakhir rendah yang ditetapkan ke biner 11111111, atau desimal -1.


Jelas bukan contoh pemrograman yang bagus.

Bahwa fungsi kerja dari Apple lebih baik

for ( ; *s1 == *s2; s1++, s2++)
    if (*s1 == '\0')
        return 0;
return ((*(unsigned char *)s1 < *(unsigned char *)s2) ? -1 : +1);

(Linux melakukannya dalam kode assembly ...)


24
2018-01-18 16:46



Sebenarnya, perbedaan harus dilakukan setidaknya 16 bit¹ karena alasan yang jelas bahwa kisaran hasilnya adalah -255 hingga 255 dan itu tidak sesuai dalam 8 bit. Namun, sfstewman benar dalam mencatat bahwa itu akan terjadi karena promosi integer implisit pula.

Pemeran akhirnya menjadi 8 bit salah, karena dapat meluap karena kisarannya masih tidak cocok dalam 8 bit. Dan bagaimanapun, strcmp memang seharusnya kembali polos int.


¹ 9 akan cukup, tetapi bit biasanya datang dalam batch 8.


9
2018-01-18 16:28



Data input unsigned 8-bit, jadi untuk menghindari pemotongan dan efek overflow / underflow, harus dikonversi ke setidaknya 9-bit yang ditandatangani, oleh karena itu int16 digunakan.


3
2018-01-18 16:27



return (int8_t)( (int16_t)*s1 - (int16_t)*s2 );

Ini bisa berarti salah satu dari dua opsi ini:

  • Entah programmer itu bingung tentang bagaimana promosi tipe implisit bekerja di C. Kedua operand secara implisit akan dikonversi inttidak peduli gipsnya int16_t. Jadi jika intmisalnya 32 bit, kode itu tidak masuk akal. Atau sebaliknya jika int setara dengan int16_t untuk sistem spesifik - maka tidak ada konversi sama sekali terjadi.

  • Atau programmer sangat paham tentang cara kerja jenis promosi dan menulis kode yang perlu dikonfirmasi ke standar yang melarang jenis promosi implisit, seperti MISRA-C. Dalam hal ini, dan jaga-jaga int adalah 16 bit pada sistem yang diberikan, kode itu masuk akal: itu memaksa jenis promosi eksplisit untuk menghindari peringatan dari kompilator / analisa statis.

Saya akan menebak bahwa opsi kedua adalah yang paling mungkin, dan bahwa kode ini ditujukan untuk sistem mikrokontroler kecil.


2
2018-01-18 16:30



Ada nilai-nilai tertentu yang akan menyebabkan perbedaan antara dua angka menjadi berbeda jika int16_t tidak ada karena meluap. Dalam sebuah int8_t rentang Anda adalah -128 hingga 127, dalam a uint8_t rentang Anda adalah 0 hingga 255, dan dalam int16_t kisaran Anda akan -32,768 hingga 32,767.

Casing ke sebuah int8_t dari uint8_t akan menyebabkan nilai di atas 127 untuk mengubah tanda karena meluap sehingga hal ini membuat hal itu terjadi, namun hasilnya harus berupa int16_t karena jika Anda memiliki hasil 255 - 0, itu akan menjadi pengembalian terpotong.


1
2018-01-18 16:32