Jika suatu angka terlalu besar, apakah angka itu tumpah ke lokasi memori berikutnya?

30

Saya telah meninjau pemrograman C dan hanya ada beberapa hal yang mengganggu saya.

Mari kita ambil kode ini sebagai contoh:

int myArray[5] = {1, 2, 2147483648, 4, 5};
int* ptr = myArray;
int i;
for(i=0; i<5; i++, ptr++)
    printf("\n Element %d holds %d at address %p", i, myArray[i], ptr);

Saya tahu bahwa int dapat memiliki nilai maksimum positif 2.147.483.647. Jadi dengan pergi satu ke itu, apakah itu "tumpah" ke alamat memori berikutnya yang menyebabkan elemen 2 muncul sebagai "-2147483648" di alamat itu? Tapi kemudian itu tidak masuk akal karena dalam output masih mengatakan bahwa alamat berikutnya memegang nilai 4, lalu 5. Jika nomor tersebut telah tumpah ke alamat berikutnya maka tidak akan mengubah nilai yang disimpan di alamat itu ?

Saya samar-samar ingat dari pemrograman di Majelis MIPS dan menonton alamat mengubah nilai selama program langkah demi langkah bahwa nilai yang ditugaskan ke alamat tersebut akan berubah.

Kecuali jika saya salah mengingat maka berikut adalah pertanyaan lain: Jika nomor yang ditugaskan ke alamat tertentu lebih besar dari jenisnya (seperti di myArray [2]) maka apakah itu tidak mempengaruhi nilai yang disimpan di alamat berikutnya?

Contoh: Kami memiliki int myNum = 4 miliar di alamat 0x10010000. Tentu saja myNum tidak dapat menyimpan 4 miliar sehingga muncul sebagai angka negatif di alamat itu. Meskipun tidak dapat menyimpan jumlah besar ini, itu tidak berpengaruh pada nilai yang disimpan di alamat berikutnya 0x10010004. Benar?

Alamat memori hanya memiliki ruang yang cukup untuk menampung ukuran angka / karakter tertentu, dan jika ukurannya melampaui batas maka akan direpresentasikan secara berbeda (seperti mencoba menyimpan 4 miliar ke int tetapi akan muncul sebagai angka negatif) dan sehingga tidak berpengaruh pada angka / karakter yang tersimpan di alamat selanjutnya.

Maaf jika saya berlebihan. Saya sudah memiliki otak besar kentut sepanjang hari dari ini.

architecture c memory hexadecimal kekar
sumber
10
Anda mungkin menjadi bingung dengan overruns string .
Robbie Dee
19
Pekerjaan rumah: Ubah CPU sederhana agar tidak tumpah. Anda akan melihat bahwa logika menjadi jauh lebih kompleks, semua untuk "fitur" yang akan menjamin lubang keamanan di mana-mana tanpa berguna di tempat pertama.
phihag
4
Jika Anda membutuhkan angka yang sangat besar, dimungkinkan untuk memiliki representasi angka yang meningkatkan jumlah memori yang digunakan agar sesuai dengan angka besar. Prosesor itu sendiri tidak dapat melakukan ini, dan itu bukan fitur dari bahasa C, tetapi perpustakaan dapat mengimplementasikannya - perpustakaan C yang umum adalah perpustakaan aritmatika Presisi Ganda GNU . Perpustakaan harus mengelola memori untuk menyimpan angka-angka yang memiliki biaya kinerja di atas aritmatika. Banyak bahasa memiliki hal semacam ini bawaan (yang tidak menghindari biaya).
Steve314
1
menulis tes sederhana, saya bukan programmer C tetapi sesuatu di sepanjang baris int c = INT.MAXINT; c+=1;dan lihat apa yang terjadi pada c.
JonH
2
@ JonH: Masalahnya adalah bahwa melimpah di Perilaku Tidak Terdefinisi. Kompiler AC dapat menemukan kode itu, dan menyimpulkan bahwa itu adalah kode yang tidak dapat dijangkau karena tanpa syarat meluap. Karena kode yang tidak terjangkau tidak penting, maka kode tersebut dapat dihilangkan. Hasil akhir: tidak ada kode yang tersisa.
MSalters

Jawaban:

48

Tidak. Di C, variabel memiliki set alamat memori yang tetap untuk dikerjakan. Jika Anda bekerja pada sistem dengan 4-byte ints, dan Anda mengatur intvariabel untuk 2,147,483,647kemudian menambahkan 1, variabel biasanya akan berisi -2147483648. (Pada kebanyakan sistem. Perilaku ini sebenarnya tidak terdefinisi.) Tidak ada lokasi memori lain yang akan dimodifikasi.

Intinya, kompiler tidak akan membiarkan Anda menetapkan nilai yang terlalu besar untuk tipe tersebut. Ini akan menghasilkan kesalahan kompiler. Jika Anda memaksakannya menggunakan case, nilainya akan terpotong.

Dilihat dengan cara bitwise, jika jenisnya hanya dapat menyimpan 8 bit, dan Anda mencoba untuk memaksa nilai 1010101010101ke dalamnya dengan case, Anda akan berakhir dengan 8 bit terbawah, atau 01010101.

Dalam contoh Anda, apa pun yang Anda lakukan myArray[2], myArray[3]akan berisi '4'. Tidak ada "tumpahan". Anda mencoba untuk meletakkan sesuatu yang lebih dari 4-byte, itu hanya akan memotong segala sesuatu di ujung yang tinggi, meninggalkan bagian bawah 4 byte. Pada kebanyakan sistem, ini akan menghasilkan -2147483648.

Dari sudut pandang praktis, Anda ingin memastikan ini tidak pernah terjadi. Jenis luapan seperti ini sering mengakibatkan cacat yang sulit dipecahkan. Dengan kata lain, jika Anda berpikir ada peluang sama sekali nilai Anda akan mencapai miliaran, jangan gunakan int.

Gort the Robot
sumber
52
Jika Anda bekerja pada sistem dengan 4 byte int, dan Anda menetapkan variabel int menjadi 2.147.483.647 dan kemudian menambahkan 1, variabel tersebut akan berisi -2147483648. => Tidak , ini adalah Perilaku Tidak Terdefinisi , jadi mungkin berputar atau mungkin melakukan hal lain sama sekali; Saya telah melihat kompiler mengoptimalkan pemeriksaan berdasarkan tidak adanya overflow dan mendapat loop tak terbatas misalnya ...
Matthieu M.
Maaf ya, Anda benar. Saya seharusnya menambahkan "biasanya" di sana.
Gort the Robot
@ MatthieuM dari perspektif bahasa , itu benar. Dalam hal eksekusi pada sistem tertentu, yang kita bicarakan di sini, itu omong kosong.
hobbs
@obb: Masalahnya adalah ketika kompiler membuat program karena perilaku tidak terdefinisi, sebenarnya menjalankan program memang akan menghasilkan perilaku yang tidak terduga, sebanding dengan efek pada memori yang ditimpa.
Matthieu M.
24

Overflow integer yang ditandatangani adalah perilaku yang tidak terdefinisi. Jika ini terjadi, program Anda tidak valid. Kompiler tidak diharuskan untuk memeriksa ini untuk Anda, sehingga dapat menghasilkan executable yang tampaknya melakukan sesuatu yang masuk akal, tetapi tidak ada jaminan bahwa itu akan dilakukan.

Namun, integer overflow unsigned didefinisikan dengan baik. Ini akan membungkus modulo UINT_MAX +1. Memori yang tidak ditempati oleh variabel Anda tidak akan terpengaruh.

Lihat juga https://stackoverflow.com/q/18195715/951890

Vaughn Cato
sumber
ditandatangani integer overflow sama jelasnya seperti integer overflow yang tidak ditandatangani. jika kata tersebut memiliki $ N $ bit, batas atas dari integer overflow yang ditandatangani adalah pada $ 2 ^ {N-1} -1 $$ (di mana ia membungkus $ -2 ^ {N-1} $) sedangkan batas atas untuk integer overflow unsigned adalah pada $$ 2 ^ N - 1 $$ (di mana ia membungkus sekitar $ 0 $). mekanisme yang sama untuk penambahan dan pengurangan, ukuran kisaran angka yang sama ($ 2 ^ N $) yang dapat direpresentasikan. hanya batas berbeda dari luapan.
robert bristow-johnson
1
@ robertbristow-johnson: Tidak sesuai dengan standar C.
Vaughn Cato
well, standar kadang-kadang ketinggalan zaman. melihat referensi SO, ada satu komentar yang langsung mengenai: "Catatan penting di sini adalah bahwa tidak ada arsitektur di dunia modern yang menggunakan apa pun selain aritmatika bertanda tangan 2 yang melengkapi. Bahwa standar bahasa masih memungkinkan untuk implementasi pada misalnya PDP-1 adalah artefak sejarah murni. - Andy Ross 12 Agustus 13 pada 20:12 "
robert bristow-johnson
saya kira itu tidak dalam standar C, tapi saya kira mungkin ada implementasi di mana aritmatika biner biasa tidak digunakan int. Kurasa mereka bisa menggunakan kode Gray atau BCD atau EBCDIC . Entah mengapa ada orang yang mendesain perangkat keras untuk melakukan aritmatika dengan kode Gray atau EBCDIC, tapi sekali lagi, saya tidak tahu mengapa ada orang yang melakukan unsigneddengan biner dan menandatangani intdengan apa pun selain komplemen 2's.
robert bristow-johnson
14

Jadi, ada dua hal di sini:

  • tingkat bahasa: apa yang dimaksud dengan semantik C
  • level mesin: apa semantik perakitan / CPU yang Anda gunakan

Di tingkat bahasa:

Dalam C:

  • overflow dan underflow didefinisikan sebagai modulo aritmatika untuk bilangan bulat tak bertanda , sehingga nilainya "loop"
  • overflow dan underflow adalah Perilaku Tidak Terdefinisi untuk bilangan bulat yang ditandatangani , sehingga apa pun bisa terjadi

Bagi mereka yang menginginkan contoh "apa pun", saya telah melihat:

for (int i = 0; i >= 0; i++) {
    ...
}

berubah menjadi:

for (int i = 0; true; i++) {
    ...
}

dan ya, ini adalah transformasi yang sah.

Ini berarti bahwa memang ada potensi risiko menimpa memori pada overflow karena beberapa transformasi kompiler yang aneh.

Catatan: pada penggunaan Dentang atau gcc -fsanitize=undefineddi Debug untuk mengaktifkan Sanitizer Perilaku Tidak Terdefinisi yang akan batal pada saat underflow / overflow dari bilangan bulat yang ditandatangani.

Atau itu berarti Anda bisa menimpa memori dengan menggunakan hasil operasi untuk mengindeks (tidak dicentang) ke dalam array. Sayangnya ini jauh lebih mungkin terjadi tanpa adanya deteksi underflow / overflow.

Catatan: pada penggunaan Dentang atau gcc -fsanitize=addressdi Debug untuk mengaktifkan Sanitizer Alamat yang akan membatalkan akses di luar batas.

Di tingkat mesin :

Itu sangat tergantung pada instruksi perakitan dan CPU yang Anda gunakan:

  • pada x86, ADD akan menggunakan 2 komplemen pada overflow / underflow, dan mengatur OF (Overflow Flag)
  • pada Mill CPU mendatang, akan ada 4 mode overflow yang berbeda untuk Add:
    • Modulo: Modulo 2-pelengkap
    • Trap: perangkap dihasilkan, menghentikan perhitungan
    • Saturate: nilai macet ke min saat underflow atau max on overflow
    • Lebar Ganda: hasilnya dihasilkan dalam register lebar ganda

Perhatikan bahwa apakah hal-hal terjadi dalam register atau memori, dalam kedua kasus CPU tidak menimpa memori pada overflow.

Matthieu M.
sumber
Apakah tiga mode terakhir ditandatangani? (Tidak masalah untuk yang pertama, karena ini 2-pelengkap.)
Deduplicator
1
@Dupuplikator: Menurut Pengantar Model Pemrograman CPU CPU, ada opcode yang berbeda untuk penambahan yang ditandatangani dan tambahan yang tidak ditandatangani; Saya berharap bahwa kedua opcodes akan mendukung 4 mode (dan dapat beroperasi pada berbagai bit-lebar dan skalar / vektor). Kemudian lagi, ini perangkat keras uap untuk saat ini;)
Matthieu M.
4

Untuk menjawab lebih lanjut @ StevenBurnap, alasan ini terjadi adalah karena cara kerja komputer pada level mesin.

Array Anda disimpan dalam memori (misalnya dalam RAM). Ketika operasi aritmatika dilakukan, nilai dalam memori disalin ke register input dari rangkaian yang melakukan aritmatika (ALU: Unit Logika Aritmatika ), operasi kemudian dilakukan pada data dalam register input, menghasilkan hasil dalam register keluaran. Hasil ini kemudian disalin kembali ke memori pada alamat yang benar dalam memori, meninggalkan area memori lain yang tidak tersentuh.

Pharap
sumber
4

Pertama (dengan asumsi standar C99), Anda mungkin ingin memasukkan <stdint.h>header standar dan menggunakan beberapa jenis yang didefinisikan di sana, terutama int32_tyang merupakan integer bertanda 32 bit, atau uint64_tyang persis integer 64 bit tanpa tanda, dan sebagainya. Anda mungkin ingin menggunakan tipe seperti int_fast16_tuntuk alasan kinerja.

Baca jawaban lain yang menjelaskan bahwa aritmatika yang tidak ditandatangani tidak pernah tumpah (atau meluap) ke lokasi memori yang berdekatan. Waspadalah terhadap perilaku tidak terdefinisi pada luapan yang ditandatangani .

Kemudian, jika Anda perlu untuk menghitung persis angka integer besar (misalnya Anda ingin menghitung faktorial 1000 dengan semua 2568 digit dalam desimal), Anda ingin bigints alias nomor presisi sewenang-wenang (atau bignums). Algoritma untuk aritmatika bigint yang efisien sangat cerdas, dan biasanya membutuhkan penggunaan instruksi mesin khusus (misalnya beberapa kata tambah dengan carry, jika prosesor Anda memilikinya). Karenanya saya sangat menyarankan dalam hal ini untuk menggunakan beberapa perpustakaan bigint yang ada seperti GMPlib

Basile Starynkevitch
sumber