Dumaloq siljish - Circular shift

Matritsalar 8 elementli dumaloq siljishlar chapga va o'ngga

Yilda kombinatorial matematika, a dumaloq siljish a-dagi yozuvlarni qayta tartibga solish operatsiyasi panjara, yoki oxirgi yozuvni birinchi holatga o'tkazish orqali, boshqa barcha yozuvlarni keyingi holatga o'tkazishda yoki teskari operatsiyani bajarish orqali. Dumaloq siljish - bu maxsus turdagi tsiklik almashtirish, bu o'z navbatida maxsus turdagi almashtirish. Rasmiy ravishda dumaloq siljish a almashtirish ning σ n katakchadagi yozuvlar shunday

{ displaystyle sigma (i) equiv (i + 1)}

modul n, barcha yozuvlar uchun men = 1, ..., n

yoki

{ displaystyle sigma (i) equiv (i-1)}

modul n, barcha yozuvlar uchun men = 1, ..., n.

Berilgan katakka dumaloq siljishlarni qayta-qayta qo'llash natijasi ham deyiladi dumaloq siljishlar panjara.

Masalan, to'rtburchakka bir necha marta dumaloq siljishlarni qo'llash (a, b, v, d) ketma-ket beradi

(d, a, b, v),
(v, d, a, b),
(b, v, d, a),
(a, b, v, d) (asl to'rt karra),

va keyin ketma-ketlik takrorlanadi; shuning uchun bu to'rt karra to'rtta aylana siljishlariga ega. Biroq, barchasi hammasi emas n- juftliklar bor n aniq aylanma siljishlar. Masalan, 4-karra (a, b, a, b) faqat 2 ta aniq aylana siljishlariga ega. Umuman olganda $ an $ ning dairesel siljishlar soni n-tupl har qanday bo'lishi mumkin bo'luvchi ning n, katak yozuvlariga qarab.

Yilda kompyuter dasturlash, a bitli aylanish, shuningdek, dumaloq siljish deb nomlanuvchi, uning operandining barcha bitlarini siljitadigan bitli operatsiya. Dan farqli o'laroq arifmetik siljish, dumaloq siljish raqamning belgi bitini saqlamaydi yoki a ni ajratmaydi suzuvchi nuqta raqami "s ko'rsatkich undan ahamiyatli va. A dan farqli o'laroq mantiqiy siljish, bo'sh bit pozitsiyalari nol bilan to'ldirilmaydi, lekin ketma-ketlikdan siljigan bitlar bilan to'ldiriladi.

Dumaloq siljishlarni amalga oshirish

Dairesel siljishlar ko'pincha ishlatiladi kriptografiya bit ketma-ketliklarini buzish uchun. Afsuski, ko'plab dasturlash tillari, shu jumladan C, deyarli barchasi bo'lsa ham, aylana siljish uchun operatorlar yoki standart funktsiyalar mavjud emas protsessorlar bor bitli operatsiya buning uchun ko'rsatmalar (masalan, Intel x86 Biroq, ba'zi kompilyatorlar protsessor ko'rsatmalariga quyidagi vositalar orqali kirishni ta'minlashi mumkin ichki funktsiyalar. Bundan tashqari, standart ANSI C kodidagi ba'zi konstruktsiyalar kompilyator tomonidan shunday ko'rsatmaga ega bo'lgan protsessorlarda "aylantirish" assotsiatsiyasi tili buyrug'i uchun optimallashtirilishi mumkin. Ko'pgina kompilyatorlar quyidagi iborani taniydilar va uni bitta 32-bitli aylantirish buyrug'i bilan kompilyatsiya qiladilar.^[1]^[2]

/* * Shiftdagi operatsiyalar faqat o'zgaruvchan qiymatlar uchun belgilanadi * manfiy emas va sizeof (value) dan kichik * CHAR_BIT. * Bit-va (&) bilan ishlatiladigan niqob aniqlanmagan xatti-harakatlarning oldini oladi * siljishlar soni 0 yoki> = imzosiz int kengligi bo'lganda. */# shu jumladan  // uchun uint32_t uchun, int kattaligidan qat'i nazar, 32 bitli kenglikdagi aylanishlarni olish.# shu jumladan CHAR_BIT uchun  //uint32_t rotl32 (uint32_t qiymat, imzosiz int hisoblash) {    konst imzosiz int niqob = CHAR_BIT * o'lchamlari(qiymat) - 1;    hisoblash &= niqob;    qaytish (qiymat << hisoblash) | (qiymat >> (-hisoblash & niqob));}uint32_t rotr32 (uint32_t qiymat, imzosiz int hisoblash) {    konst imzosiz int niqob = CHAR_BIT * o'lchamlari(qiymat) - 1;    hisoblash &= niqob;    qaytish (qiymat >> hisoblash) | (qiymat << (-hisoblash & niqob));}

Ushbu xavfsiz va kompilyatorga mos dastur tomonidan ishlab chiqilgan Jon Regehr,^[3] va Piter Kordes tomonidan yanada sayqallangan.^[4]^[5]

Oddiy versiyasi ko'pincha hisoblash 1 dan 31 bit oralig'ida cheklangan:

uint32_t rotl32 (uint32_t qiymat, imzosiz int hisoblash) {    qaytish qiymat << hisoblash | qiymat >> (32 - hisoblash);}

Ushbu versiya xavfli, chunki agar hisoblash 0 yoki 32 bo'lsa, u 32-bitli almashtirishni so'raydi, ya'ni aniqlanmagan xatti-harakatlar C tili standartida. Biroq, u baribir ishlashga intiladi, chunki ko'pchilik mikroprotsessorlar buni amalga oshiradilar qiymati >> 32 yoki 32-bitli o'zgarish (0-ni ishlab chiqarish) yoki 0-bitli almashtirish (asl nusxani ishlab chiqarish) qiymat) va ikkalasi ham ushbu dasturda to'g'ri natijani beradi.

Misol

Agar bit ketma-ketligi 0001 0111 bitta bit pozitsiyasining dumaloq siljishiga duch kelgan bo'lsa ... (quyidagi rasmlarga qarang)

chapga hosil bo'ladi: 0010 1110

Chap dumaloq siljish.

o'ng tomonga hosil bo'ladi: 1000 1011.

O'ng dumaloq siljish.

Agar 1001 0110 bit ketma-ketligi quyidagi operatsiyalarga uchragan bo'lsa:

chap tomonga 1 pozitsiyaga siljish:	0010 1101
chap dumaloq siljish 2 pozitsiyaga:	0101 1010
chap dumaloq siljish 3 pozitsiyaga:	1011 0100
chap dumaloq siljish 4 pozitsiyaga:	0110 1001
5 ta pozitsiyaga chap aylana siljishi:	1101 0010
chap dumaloq siljish 6 pozitsiyaga:	1010 0101
chap dumaloq siljish 7 pozitsiyaga:	0100 1011
8 dumaloq chap dumaloq siljish:	1001 0110

1 pozitsiyaga o'ng dairesel siljish:	0100 1011
o'ng dumaloq siljish 2 pozitsiyaga:	1010 0101
3 ta pozitsiyaga o'ng dumaloq siljish:	1101 0010
to'rtta pozitsiyaga o'ng dumaloq siljish:	0110 1001
5 ta pozitsiyaga o'ng dumaloq siljish:	1011 0100
6 dumaloqqa o'ng dumaloq siljish:	0101 1010
7 pozitsiyaga o'ng dumaloq siljish:	0010 1101
8 ta pozitsiyaga o'ng dumaloq siljish:	1001 0110

Ilovalar

Tsiklik kodlar bir xil blok kodi kod so'zining dumaloq siljishi har doim boshqa kod so'zini beradigan xususiyatga ega. Bu quyidagi umumiy ta'rifni rag'batlantiradi: a mag'lubiyat s alifbo orqali Σ, ruxsat bering siljish(s) ni belgilang o'rnatilgan ning dumaloq siljishlari sva to'plam uchun L iplar, ruxsat bering siljish(L) satrlarning barcha dumaloq siljishlarining to'plamini belgilang L. Agar L bu tsiklik kod, keyin siljish(L) ⊆ L; bu uchun zarur shart L bo'lish a tsiklik til. Amaliyot siljish(L) da o'rganilgan rasmiy til nazariyasi. Masalan, agar L a kontekstsiz til, keyin siljish(L) yana kontekstsiz.^[6]^[7] Bundan tashqari, agar L tomonidan tasvirlangan doimiy ifoda uzunlik n, uzunlikning doimiy ifodasi mavjud O (n³) tasvirlab beradi siljish(L).^[8]

Shuningdek qarang

Barrelni almashtirish
Bit-bitli operatsiya
Sirkulant
Lyndon so'zi
Marjonlarni - a kabi ob'ekt panjara ammo aylanma siljishlar ekvivalent deb hisoblanadi.

Adabiyotlar

^ GKK: "Umumiy rotatsion konstruktsiyalarni optimallashtirish"
^ "ROTL / ROTR DAG birlashtiruvchi kodidagi tozalash" ushbu kod CellSPU-da "aylantirish" ko'rsatmasini qo'llab-quvvatlashini eslatib o'tadi
^ C / C ++ da xavfsiz, samarali va ko'chma aylantirish
^ Stackoverflow: C / C ++ da aylantirish uchun eng yaxshi amaliyot
^ Taxminan doimiy vaqtni aylantiring, bu standartlarni buzmaydi
^ T. Oshiba, "Kontekstsiz tillar oilasining yopilish xususiyati" tsiklli siljish operatsiyasi ostida ", IECE Transactionlar, 55D:119–122, 1972.
^ A. N. Maslov, "Tillar uchun tsiklik smenada ishlash", Axborot uzatish muammolari 9:333–338, 1973.
^ Gruber, German; Xoltser, Markus (2009). "Polinom kattaligining doimiy ifodalari bilan til operatsiyalari" (PDF). Nazariy kompyuter fanlari. 410 (35): 3281–3289. doi:10.1016 / j.tcs.2009.04.009. Zbl 1176.68105. Arxivlandi asl nusxasi (PDF) 2017-08-29. Olingan 2012-09-06..

[1] GKK: "Umumiy rotatsion konstruktsiyalarni optimallashtirish"

[2] "ROTL / ROTR DAG birlashtiruvchi kodidagi tozalash" ushbu kod CellSPU-da "aylantirish" ko'rsatmasini qo'llab-quvvatlashini eslatib o'tadi

[3] C / C ++ da xavfsiz, samarali va ko'chma aylantirish

[4] Stackoverflow: C / C ++ da aylantirish uchun eng yaxshi amaliyot

[5] Taxminan doimiy vaqtni aylantiring, bu standartlarni buzmaydi

[6] T. Oshiba, "Kontekstsiz tillar oilasining yopilish xususiyati" tsiklli siljish operatsiyasi ostida ", IECE Transactionlar, 55D:119–122, 1972.

[7] A. N. Maslov, "Tillar uchun tsiklik smenada ishlash", Axborot uzatish muammolari 9:333–338, 1973.

[8] Gruber, German; Xoltser, Markus (2009). "Polinom kattaligining doimiy ifodalari bilan til operatsiyalari" (PDF). Nazariy kompyuter fanlari. 410 (35): 3281–3289. doi:10.1016 / j.tcs.2009.04.009. Zbl 1176.68105. Arxivlandi asl nusxasi (PDF) 2017-08-29. Olingan 2012-09-06..

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]