Sign overflow di C ++ dan undefined behaviour (UB)

Saya ingin tahu tentang penggunaan kode seperti berikut ini

int result = 0;
int factor = 1;
for (...) {
    result = ...
    factor *= 10;
}
return result;

Jika loop berulang nkali, kemudian factordikalikan dengan waktu yang 10tepat n. Namun, factorhanya pernah digunakan setelah dikalikan 10total n-1kali. Jika kita berasumsi bahwa factortidak pernah meluap kecuali pada iterasi terakhir dari loop, tetapi mungkin meluap pada iterasi terakhir dari loop, maka haruskah kode tersebut dapat diterima? Dalam hal ini, nilai factorterbukti tidak akan pernah digunakan setelah luapan terjadi.

Saya sedang berdebat tentang apakah kode seperti ini harus diterima. Dimungkinkan untuk menempatkan perkalian di dalam pernyataan if dan tidak melakukan perkalian pada iterasi terakhir dari loop ketika itu bisa meluap. The downside adalah bahwa itu mengacaukan kode dan menambahkan cabang yang tidak perlu yang perlu memeriksa semua iterasi loop sebelumnya. Saya juga bisa mengulangi loop satu kali lebih sedikit dan mereplikasi loop body sekali setelah loop, sekali lagi, ini menyulitkan kode.

Kode aktual yang dimaksud digunakan dalam loop-ketat yang mengkonsumsi sebagian besar waktu CPU total dalam aplikasi grafis real-time.

Compiler menganggap bahwa program C ++ yang valid tidak mengandung UB. Pertimbangkan misalnya:

if (x == nullptr) {
    *x = 3;
} else {
    *x = 5;
}

Jika x == nullptrkemudian dereferencing dan menugaskan nilai adalah UB. Oleh karena itu satu-satunya cara ini bisa berakhir dalam program yang valid adalah ketika x == nullptrtidak akan pernah menghasilkan true dan kompiler dapat mengasumsikan di bawah aturan seolah-olah, di atas setara dengan:

*x = 5;

Sekarang dalam kode Anda

int result = 0;
int factor = 1;
for (...) {      // Loop until factor overflows but not more
   result = ...
   factor *= 10;
}
return result;

Perkalian terakhir factortidak dapat terjadi dalam program yang valid (limpahan yang ditandatangani tidak ditentukan). Karenanya tugas untuk resulttidak dapat terjadi. Karena tidak ada cara untuk bercabang sebelum iterasi terakhir juga iterasi sebelumnya tidak dapat terjadi. Akhirnya, bagian dari kode yang benar (yaitu, tidak ada perilaku tidak terdefinisi yang pernah terjadi) adalah:

// nothing :(

Perilaku intoverflow tidak ditentukan.

Tidak masalah jika Anda membaca di factorluar lingkaran; jika sudah meluap saat itu maka perilaku kode Anda pada, setelah, dan agak paradoks sebelum overflow tidak terdefinisi.

Salah satu masalah yang mungkin timbul dalam menjaga kode ini adalah bahwa kompiler semakin agresif ketika datang ke optimasi. Khususnya mereka mengembangkan kebiasaan di mana mereka menganggap bahwa perilaku tidak terdefinisi tidak pernah terjadi. Agar hal ini terjadi, mereka dapat menghapus forloop sama sekali.

Tidak bisakah Anda menggunakan unsignedtipe untuk factorsementara Anda perlu khawatir tentang konversi yang tidak diinginkan intke unsigneddalam ekspresi yang mengandung keduanya?

Mungkin bijaksana untuk mempertimbangkan pengoptimal dunia nyata. Loop membuka gulungan adalah teknik yang dikenal. Ide dasar op loop membuka gulungan adalah itu

for (int i = 0; i != 3; ++i)
    foo()

mungkin lebih baik diimplementasikan di belakang layar sebagai

 foo()
 foo()
 foo()

Ini adalah kasus yang mudah, dengan batas yang tetap. Tetapi kompiler modern juga dapat melakukan ini untuk batasan variabel:

for (int i = 0; i != N; ++i)
   foo();

menjadi

__RELATIVE_JUMP(3-N)
foo();
foo();
foo();

Jelas ini hanya berfungsi jika kompiler mengetahui bahwa N <= 3. Dan di situlah kita kembali ke pertanyaan awal. Karena kompiler tahu bahwa overflow yang ditandatangani tidak terjadi , ia tahu bahwa loop dapat mengeksekusi maksimum 9 kali pada arsitektur 32 bit. 10^10 > 2^32. Karena itu ia dapat melakukan loop iterasi 9 membuka gulungan. Tapi maksimum yang dimaksud adalah 10 iterasi! .

Apa yang mungkin terjadi adalah bahwa Anda mendapatkan lompatan relatif ke instruksi perakitan (9-N) dengan N = 10, sehingga offset -1, yang merupakan instruksi lompatan itu sendiri. Ups. Ini adalah optimalisasi loop yang benar-benar valid untuk C ++ yang didefinisikan dengan baik, tetapi contoh yang diberikan berubah menjadi loop tak terbatas yang ketat.

Setiap bilangan bulat bilangan bulat yang ditandatangani menghasilkan perilaku yang tidak terdefinisi, terlepas dari apakah nilai meluap itu atau mungkin dibaca.

Mungkin dalam use-case Anda, Anda dapat mengangkat iterasi pertama dari loop, memutarnya

int result = 0;
int factor = 1;
for (int n = 0; n < 10; ++n) {
    result += n + factor;
    factor *= 10;
}
// factor "is" 10^10 > INT_MAX, UB

dalam hal ini

int factor = 1;
int result = 0 + factor; // first iteration
for (int n = 1; n < 10; ++n) {
    factor *= 10;
    result += n + factor;
}
// factor is 10^9 < INT_MAX

Dengan optimisasi diaktifkan, kompiler mungkin membuka gulungan lingkaran kedua di atas menjadi satu lompatan bersyarat.

Ini adalah UB; dalam istilah ISO C ++ seluruh perilaku seluruh program sepenuhnya tidak ditentukan untuk eksekusi yang pada akhirnya menyentuh UB. Contoh klasik adalah sejauh standar C ++ peduli, itu dapat membuat setan terbang keluar dari hidung Anda. (Saya sarankan agar tidak menggunakan implementasi di mana setan hidung adalah kemungkinan nyata). Lihat jawaban lain untuk lebih jelasnya.

Compiler dapat "menyebabkan masalah" pada waktu kompilasi untuk jalur eksekusi yang dapat mereka lihat mengarah ke kompilasi-waktu-terlihat UB, misalnya menganggap blok-blok dasar itu tidak pernah tercapai.

Lihat juga Apa yang Harus Diketahui Setiap Pemrogram C Tentang Perilaku Tidak Terdefinisi (blog LLVM). Sebagaimana dijelaskan di sana, UB yang ditandai-limpahkan memungkinkan penyusun membuktikan bahwa for(... i <= n ...)loop bukan loop yang tak terbatas, bahkan untuk yang tidak dikenal n. Ini juga memungkinkan mereka "mempromosikan" penghitung loop int ke penunjuk lebar alih-alih mengulang ekstensi tanda. (Jadi konsekuensi dari UB dalam hal ini dapat mengakses di luar elemen 64k atau 4G rendah dari sebuah array, jika Anda mengharapkan pembungkus masuk ike dalam kisaran nilainya.)

Dalam beberapa kasus, kompiler akan mengeluarkan instruksi ilegal seperti x86 ud2untuk blok yang dapat menyebabkan UB jika pernah dieksekusi. (Perhatikan bahwa suatu fungsi mungkin tidak pernah dipanggil, sehingga kompiler pada umumnya tidak dapat mengamuk dan merusak fungsi lainnya, atau bahkan jalur yang mungkin melalui fungsi yang tidak mengenai UB. Yaitu kode mesin yang dikompilasi harus tetap berfungsi untuk semua input yang tidak mengarah ke UB.)

Mungkin solusi yang paling efisien adalah dengan mengupas iterasi terakhir secara manual sehingga yang tidak dibutuhkan factor*=10dapat dihindari.

int result = 0;
int factor = 1;
for (... i < n-1) {   // stop 1 iteration early
    result = ...
    factor *= 10;
}
 result = ...      // another copy of the loop body, using the last factor
 //   factor *= 10;    // and optimize away this dead operation.
return result;

Atau jika badan loop besar, pertimbangkan untuk menggunakan tipe unsigned untuk factor. Kemudian Anda dapat membiarkan berlipat ganda unsigned dan itu hanya akan melakukan pembungkusan yang didefinisikan dengan baik untuk beberapa kekuatan 2 (jumlah bit nilai dalam jenis unsigned).

Ini baik-baik saja walaupun Anda menggunakannya dengan tipe yang ditandatangani, terutama jika konversi Anda yang ditandatangani-> tidak pernah meluap.

Konversi antara unsigned dan komplemen 2's ditandatangani gratis (pola bit yang sama untuk semua nilai); modulo wrapping untuk int -> unsigned yang ditentukan oleh standar C ++ menyederhanakan hanya menggunakan pola bit yang sama, tidak seperti komplemen atau tanda / magnitude seseorang.

Dan unsigned-> signed juga sepele, meskipun penerapannya ditentukan untuk nilai yang lebih besar dari INT_MAX. Jika Anda tidak menggunakan hasil besar tanpa tanda tangan dari iterasi terakhir, Anda tidak perlu khawatir. Tetapi jika ya, lihat Apakah konversi dari tidak ditandatangani menjadi ditandatangani tidak ditentukan? . Kasus nilai-tidak-cocok adalah implementasi-didefinisikan , yang berarti bahwa suatu implementasi harus memilih beberapa perilaku; yang waras hanya memotong (jika perlu) pola bit yang tidak ditandatangani dan menggunakannya sebagai ditandatangani, karena itu bekerja untuk nilai dalam kisaran dengan cara yang sama tanpa kerja tambahan. Dan jelas bukan UB. Jadi nilai unsigned yang besar bisa menjadi bilangan bulat bertanda negatif. misal setelah int x = u; gcc dan dentang jangan dioptimalkanx>=0seperti selalu benar, bahkan tanpa -fwrapv, karena mereka mendefinisikan perilaku.

Jika Anda dapat mentolerir beberapa instruksi perakitan tambahan dalam loop, alih-alih

int factor = 1;
for (int j = 0; j < n; ++j) {
    ...
    factor *= 10;
}

kamu bisa menulis:

int factor = 0;
for (...) {
    factor = 10 * factor + !factor;
    ...
}

untuk menghindari perkalian terakhir. !factortidak akan memperkenalkan cabang:

    xor     ebx, ebx
L1:                       
    xor     eax, eax              
    test    ebx, ebx              
    lea     edx, [rbx+rbx*4]      
    sete    al    
    add     ebp, 1                
    lea     ebx, [rax+rdx*2]      
    mov     edi, ebx              
    call    consume(int)          
    cmp     r12d, ebp             
    jne     .L1                   

Kode ini

int factor = 0;
for (...) {
    factor = factor ? 10 * factor : 1;
    ...
}

juga menghasilkan perakitan tanpa cabang setelah optimasi:

    mov     ebx, 1
    jmp     .L1                   
.L2:                               
    lea     ebx, [rbx+rbx*4]       
    add     ebx, ebx
.L1:
    mov     edi, ebx
    add     ebp, 1
    call    consume(int)
    cmp     r12d, ebp
    jne     .L2

(Dikompilasi dengan GCC 8.3.0 -O3)

Anda tidak menunjukkan apa yang ada di dalam tanda kurung forpernyataan, tapi saya akan berasumsi itu seperti ini:

for (int n = 0; n < 10; ++n) {
    result = ...
    factor *= 10;
}

Anda cukup memindahkan kenaikan kontra dan cek terminasi loop ke tubuh:

for (int n = 0; ; ) {
    result = ...
    if (++n >= 10) break;
    factor *= 10;
}

Jumlah instruksi perakitan dalam loop akan tetap sama.

Terinspirasi oleh presentasi Andrei Alexandrescu "Speed ​​Is Found In The Minds of People".

Pertimbangkan fungsinya:

unsigned mul_mod_65536(unsigned short a, unsigned short b)
{
  return (a*b) & 0xFFFFu;
}

Menurut Rationale yang diterbitkan, penulis Standar akan berharap bahwa jika fungsi ini dipanggil pada (misalnya) komputer 32-bit biasa dengan argumen 0xC000 dan 0xC000, mempromosikan operan *untuk signed intakan menyebabkan perhitungan menghasilkan -0x10000000 , yang ketika dikonversi unsignedakan menghasilkan 0x90000000u- jawaban yang sama seolah-olah mereka telah unsigned shortmempromosikan unsigned. Meskipun demikian, gcc terkadang akan mengoptimalkan fungsi itu dengan cara yang akan berperilaku tidak masuk akal jika terjadi overflow. Kode apa pun di mana beberapa kombinasi input dapat menyebabkan overflow harus diproses dengan -fwrapvopsi kecuali itu akan dapat diterima untuk memungkinkan pembuat input dengan sengaja salah bentuk untuk mengeksekusi kode arbitrer yang mereka pilih.

Kenapa tidak ini:

int result = 0;
int factor = 10;
for (...) {
    factor *= 10;
    result = ...
}
return result;

Ada banyak wajah berbeda dari Perilaku Tidak Terdefinisi, dan apa yang dapat diterima tergantung pada penggunaan.

loop dalam yang ketat yang menghabiskan sebagian besar waktu CPU total dalam aplikasi grafis real-time

Itu, dengan sendirinya, adalah sedikit hal yang tidak biasa, tetapi karena itu mungkin ... jika memang demikian, maka UB kemungkinan besar berada di ranah "diizinkan, dapat diterima" . Pemrograman grafik terkenal karena peretasan dan hal-hal buruk. Selama "bekerja" dan tidak butuh lebih dari 16,6 ms untuk menghasilkan bingkai, biasanya, tidak ada yang peduli. Namun tetap, waspadai apa artinya memohon UB.

Pertama, ada standarnya. Dari sudut pandang itu, tidak ada yang perlu didiskusikan dan tidak ada cara untuk membenarkan, kode Anda tidak valid. Tidak ada jika atau ketika itu, itu bukan kode yang valid. Anda mungkin juga mengatakan bahwa jari tengah dari sudut pandang Anda, dan 95-99% dari waktu Anda akan baik untuk tetap pergi.

Selanjutnya, ada sisi perangkat kerasnya. Ada beberapa arsitektur aneh dan tidak biasa di mana ini menjadi masalah. Saya mengatakan "tidak biasa, aneh" karena pada satu arsitektur yang membentuk 80% dari semua komputer (atau dua arsitektur yang bersama-sama membentuk 95% dari semua komputer) melimpah adalah "ya, apa pun, tidak peduli" hal di tingkat perangkat keras. Anda yakin mendapatkan hasil sampah (meskipun masih dapat diprediksi), tetapi tidak ada hal-hal jahat terjadi.
Itu tidakkasus pada setiap arsitektur, Anda mungkin mendapatkan jebakan overflow (meskipun melihat bagaimana Anda berbicara tentang aplikasi grafis, kemungkinan berada pada arsitektur yang aneh agak kecil). Apakah portabilitas masalah? Jika ya, Anda mungkin ingin abstain.

Terakhir, ada sisi kompiler / pengoptimal. Salah satu alasan mengapa overflow tidak terdefinisi adalah hanya membiarkannya pada saat yang paling mudah untuk mengatasi perangkat keras sekali waktu. Tapi alasan lain adalah bahwa misalnya x+1adalah dijamin untuk selalu lebih besar dari x, dan compiler / optimizer dapat memanfaatkan pengetahuan ini. Sekarang, untuk kasus yang disebutkan sebelumnya, kompiler memang dikenal untuk bertindak seperti ini dan hanya menghapus blok lengkap (ada ada exploit Linux beberapa tahun yang lalu yang didasarkan pada kompiler yang telah mati-henti menanggalkan beberapa kode validasi karena hal ini).
Untuk kasus Anda, saya akan sangat ragu bahwa kompiler melakukan beberapa optimasi khusus, aneh. Namun, apa yang Anda ketahui, apa yang saya tahu. Jika ragu, cobalah. Jika berhasil, Anda baik untuk pergi.

(Dan akhirnya, tentu saja ada audit kode, Anda mungkin harus membuang waktu untuk membahas hal ini dengan auditor jika Anda kurang beruntung.)