في عام 1984 ، صدر كتاب عبادة ستيفن ليفي ، Hackers: Heroes of the Computer Revolution . هناك ترجمة روسية للهواة ، لكنها بعيدة عن المثالية. لقد تعهدت بتصحيح عدم الدقة فيه ، ووضع النص الإنكليزي بجانبه (بالمناسبة ، وليس بدون خطيئة) ، ولكن تخلي عنه بعد الفصل الثاني. بطريقة أو بأخرى ، أود أن ألفت انتباهك إلى جزء (يمكنك قراءته في مقال منفصل ) مخصص للروتين الفرعي لطباعة رقم في نظام عشري. كم يمكن تخفيض هذا البرنامج؟ ما هو الحد؟في أغسطس 2018 ، كتبت برنامجًا لقياس وقت التنفيذ الدقيق لتعليمات المعالج السوفييتي 1801BM1 (يحتوي على مجموعة من تعليمات PDP-11 ). كان من الضروري معرفة الوقت الدقيق (في دورات المعالج) عند العمل على العرض التوضيحي " Good Apple " لجهاز الكمبيوتر BK 0011M. كنت أرغب في رؤية نتائج القياس عشرية. للقيام بذلك ، اضطررت إلى كتابة روتين فرعي الخاص بي - لم تكن وظائف النظام متاحة بسبب تفاصيل الاختبار.أول شيء فعلته هو تكوين مصفوفة TEN بسلطات 10. الإجراء يأخذ رقمًا في السجل R0 ، الإخراج هو سلسلة نصية في NUMBER. هام: لا يوجد تعليمات القسمة في المعالج ! MOV #NUMBER,R1 ; pointer to output text string
MOV #TEN,R5
1: CMP (R5)+,R0 ; skip leading zeros
BHI 1 ; branch if higher, for 16-bit not signed
MOV -(R5),R3
BEQ 4 ; if less then 10
2: MOV #47.,R4 ; 0 symbol in ASCII codepage - 1
3: INC R4 ; count digits
SUB R3,R0
BHIS 3 ; branch if higher or same, for 16-bit not signed
MOVB R4,(R1)+ ; print R4
ADD (R5)+,R0
MOV (R5),R3
BNE 2
4: ADD #48.,R0 ; 0 symbol in ASCII codepage
MOVB R0,(R1)+ ; print R0
CLRB (R1) ; end of text marker
RET
TEN: .WORD 10000.,1000.,100.,10.,0
لفهم مُجمِّع PDP-11 ، يكفي أن تتذكر أن الوسيطات مكتوبة من اليسار إلى اليمين (المصدر أولاً ، ثم جهاز الاستقبال) ، وتبدأ أوامر الفرع الشرطي بالحرف B (من كلمة الفرع - التفرع). لن أصف الخوارزمية ، فهي ليست ذات فائدة ولا تُعطى هنا إلا كنقطة انطلاق. حجم هذا الروتين هو 22 كلمة (لا تشمل البيانات).بعد أن نجح كل شيء ، تذكرت فجأة القصة من كتاب ستيفن ليفي: كافح المتسللون لتقليل حجم برنامج مماثل ، وكذلك على بنية PDP. صحيح أن لديهم PDP-1 ، ولكن بعد بضع سنوات حصلوا على PDP-11.
في افتتاح الكتاب وجدت وصفا غامضا للغاية. بدأ قراصنة من معهد ماساتشوستس للتكنولوجيامثلي من قائمة المنازل العشرية. لكن ما حدث بعد ذلك ليس واضحًا من النص. من الواضح أن هذا لم يكن واضحًا لمؤلف الكتاب أيضًا ؛ فهو ببساطة كتب الكلمات الشائعة من شفاه شهود العيان في مسابقة القرصنة.اضطررت إلى الخوض في أرشيف الإنترنت لبرامج PDP-1 . هناك الكثير من الأشياء المثيرة للاهتمام: Minskytron ، Munching الساحات وغيرها من ما يسمى ب "اختراق الاختراق" (بالمناسبة ، من الجدير بالذكر أنه في ذلك الوقت - في أوائل الستينيات - استخدم قراصنة MIT مصطلح " عرض " بنفس المعنى الذي نستخدمه الآن على demoscene). هناك العديد من إجراءات النظام في الأرشيف ، ولكن للأسف ، لا يوجد رقم عشري بينها.بعد ذلك ، مسلحًا بمُصحح ، قررت أن أرى كيف تم تنفيذ هذا الإجراء في نظام التشغيل MKDOS ، والذي أستخدمه على BK 0010 و BK 0011M. يا معجزة! - بعد النظر عن كثب ، أدركت أن البرنامج الفرعي يتناسب جيدًا مع الوصف الضبابي من كتاب "Hackers". إليك رمزها: MOV #10.,R4
CLR R2
1: CLR R1
2: SUB R4,R0 ; 10,
BLO 3
INC R1 ; -
BR 2
3: ADD R4,R0
ADD #48.,R0 ; ASCII- 0
INC R2 ; -
MOVB R0,-(SP)
MOV R1,R0 ; -
BNE 1
INC R2
MOVB #32.,-(SP) ; ASCII-
4: MOVB (SP)+,R0
CALL PRINT
SOB R2,4 ;
RET
يشكل البرنامج سلسلة نصية على المكدس ، ثم يستدعي إجراء الطباعة لكل حرف محفوظ. على ما يبدو ، هذا هو بالضبط ما كان يقصده كتاب ستيفن ليفي تحت عبارة "يتحول بالطريقة المعاكسة ، وبمساعدة برنامج ماكر ، يتم طباعته بالترتيب الصحيح." يجب أن تكون الميزات الأخرى للخوارزمية واضحة من التعليقات على الرمز.حجم الروتين 23 كلمة ، ولكن لا يمكنك مقارنته مباشرة بروتين فرعي: الشروط مختلفة للغاية. قررت إعادة تصميم البرنامج من MKDOS إلى شروطي: تشكيل سلسلة نصية في الذاكرة.في النهاية ، أدركت أنه من الأفضل ترك فكرة طرح الرقم 10 فقط ، وكتابة الباقي من البداية. بعد عدة لفات من تحسين Sansara ، حصلت على ما يلي: MOV #NUMBER,R1 ; pointer to output text string
CLRB -(R1) ; end of text marker
MOV #10.,R4
1: MOV #-1.,R5
2: INC R5 ; counter of 10s
SUB R4,R0
BHIS 2 ; branch if higher or same
ADD #58.,R0 ; #10. + '0' ASCII code
MOVB R0,-(R1) ; store R0 to text string
MOV R5,R0 ; let's count next how many 10s in number of 10s
BNE 1
RET ; returns text string pointer in R1
16 كلمة ، تم الوصول إلى الحد الأقصى (فكرت) ، ها هو - السكينة ، التي كتب عنها ستيفن ليفي عاطفياً!ما الحيل المطبقة هنا:- يقوم الأمر الأول بتعيين المؤشر ليس في البداية ، ولكن في نهاية سطر النص. يتم تعبئة النص من اليمين إلى اليسار - وهذا أيضًا مريح لأنه لأنه عند الإخراج نحصل على عنوان بداية السطر ، جاهزًا لإرساله إلى إجراء طباعة النص.
- , . (INC R5) 1. 0, , ?.. , 10 – , . , . . – . : 1 , , 1 ( ). , , . . -1.
- 10, , , . – ( ). , – . , , . ( 10 10 ) . : ASCII- 0, ! , , . ADD #58.,R0 (48+10).
لقد كنت سعيدًا جدًا بالبرنامج الذي قررت مشاركته في منتدى zx-pk.ru (لا أشك في أي شيء من التقاليد المحلية للانتقاد بدون حجج). كان رد فعل المجتمع شيئًا من هذا القبيل: "كان عليك فقط أن ترى كيف فعلوا ذلك في DEC ، إنه كلاسيكي".حسنًا ، إليك برنامج من DEC ، الشركة التي أنشأت PDP-11 وأدرجت بعض المتسللين من MIT في صفوفها:; RETURNS:
; R0 = 0
; R1 -> byte following last digit in converted number
CVBTOD: MOV R0,-(SP) ;SAVE THE NUMBER PASSED TO US
CLR R0 ;SET FOR CRUDE DIVIDE BY 10.
10$: INC R0 ;BUMP QUOTIENT
SUB #10.,(SP) ;REDUCE NUMBER BY 10.
BHIS 10$ ;IF SIGN DIDN'T CHANGE...
ADD #10.+48.,(SP) ;MAKE REMAINDER PRINTABLE
DEC R0 ;REDUCE QUOTIENT
BEQ 20$ ;IF ZERO, TIME TO PRINT
CALL CVBTOD ;OTHERWISE, RECURSE !
20$: MOVB (SP)+,(R1)+ ;STORE A CONVERTED DIGIT
RETURN ;UNWIND THE RECURSION
14 كلمة ، رائع! أم لا؟ لقد هُزمت ، لكن دعنا نلقي نظرة فاحصة:- تتم إضافة رمز ASCII للحرف 0 والرقم 10 في عملية واحدة. اتضح أنه تم استخدام هذه الحيلة في السبعينيات. رائع.
- البرنامج يطلق على نفسه بشكل متكرر - حل جميل!
- – , . – .
- R1 . , , .
- , ! ?.. , . , zx-pk.ru MOV #NUMBER,R1 !
المجموع ، الحجم الفعلي هو 16 كلمة . تمامًا مثل خاصتي. يتكون كلا البرنامجين من 12 تعليمات. إذن أيهما أفضل؟حتى إذا قمت باستبدال مكالمات مكدس بمكالمات تسجيل ، فإن برنامج DEC سيكون أبطأ بسبب تعليمات DEC R0 و CALL داخل الحلقة.لكن هذا ليس كل شيء. عندما بدأت في كتابة هذه المقالة ، لاحظت أنه في برنامجي كان هناك تعليمات بدائية (من MKDOS) MOV # 10. ، R4 - لا معنى لها سوى تسريع الحلقة الداخلية. حان الوقت للتخلص منها. MOV #NUMBER,R1 ; pointer to output text string
CLRB -(R1) ; end of text marker
1: MOV #-1.,R5
2: INC R5 ; counter of 10s
SUB #10.,R0
BHIS 2 ; branch if higher or same
ADD #58.,R0 ; #10. + '0' ASCII code
MOVB R0,-(R1) ; store R0 to text string
MOV R5,R0 ; let's count next how many 10s in number of 10s
BNE 1 ; loop if R0 is not zero
RET ; returns text string pointer in R1
15 كلمة . 11 تعليمات. الآن ، يبدو أن هذا كل شيء.حسنًا ، لقد انتهت أفكار التحسين لدي. لقد كان تحديا ملهما ، بل ومقامرا. من الجدير بالملاحظة أن الفكرة التي اقترحها هاكر طالب في أوائل الستينيات لـ PDP-1 تم استخدامها من قبل DEC عشر أو حتى عشرين عامًا ، وتم تطبيقها على الكمبيوتر السوفييتي BK 0011M حتى أوائل 2000. والمثير للدهشة ، أنه في عام 2018 ، كان من الممكن إعادة اختراع الخوارزمية وتحسينها جزئيًا. مميز ، اعتبر الكثيرون هذا مستحيلاً.لذا ، إليك الكأس المقدسة (وفقًا لستيفن ليفي) ، التي حاول قراصنة الستينيات العثور عليها - أقصر برنامج عشري لـ PDP. أو ... ربما أقصر؟تحديث: كنت أعلم أن هذا اليوم سيأتي ، لكنني لم أفكر قريبًا :) اتضح أن البرنامج يمكن تقليله بكلمة أخرى! تم اقتراح الفكرة في تعليقات Mr_Rm : MOV #NUMBER,R1 ; pointer to output text string
CLRB -(R1) ; end of text marker
1: CLR R5
2: INC R5 ; counter of 10s +1
SUB #10.,R0
BHIS 2 ; branch if higher or same
ADD #58.,R0 ; #10. + '0' ASCII code
MOVB R0,-(R1) ; store R0 to text string
MOV R5,R0 ; let's count how many 10s in number of 10s
SOB R0,1 ; subtract 1 and loop if not zero
RET ; returns text string pointer in R1
14 كلمة . 11 تعليمات.الحيلة هي هذه. تذكر ، لقد كتبت أنه مع التنظيم "الخاطئ" لدورة R5 ، يتم الحصول على واحد أكثر من اللازم؟ والسماح كذلك! سنقوم بتقليله في نهاية البرنامج. في الإصدار السابق ، تم نسخ R5 إلى R0 ، وبعد ذلك قام الأمر BNE (الفرع إذا لم يكن يساوي الصفر) بفحص R0 ، وإذا لم يكن يساوي الصفر ، فقد ذهب إلى بداية الدورة. إذا قمنا فقط بتقليل R0 بمقدار واحد ، ثم (إذا لم نحصل على صفر) ، فانتقل إلى البداية ... انتظر دقيقة ، ولكن هذا أمر عادي لدورة SOB (طرح واحد وفرع). صحيح ، هنا لم يتم استخدامها بطريقة متعارف عليها: فهي تحقق مرة واحدة ، ثم يتلاشى عداد الدراجات. يبدو هذا محبطًا ، ولكن إذا نظرت إلى الإصدار السابق من الروتين الفرعي ، يصبح من الواضح كيف يتم تقصير إصدار جديد منه.روابط مفيدة: