fungsi kode mesin x86 32-bit, 21 byte
fungsi kode mesin x86-64, 22 byte
Penghematan 1B dalam mode 32-bit membutuhkan penggunaan separator = filler-1, mis fill=0
dan sep=/
. Versi 22-byte dapat menggunakan pilihan separator dan filler yang sewenang-wenang.
Ini adalah versi 21-byte, dengan input-separator = \n
(0xa), output-filler = 0
, output-separator = /
= filler-1. Konstanta ini dapat dengan mudah diubah.
; see the source for more comments
; RDI points to the output buffer, RSI points to the src string
; EDX holds the base
; This is the 32-bit version.
; The 64-bit version is the same, but the DEC is one byte longer (or we can just mov al,output_separator)
08048080 <str_exp>:
8048080: 6a 01 push 0x1
8048082: 59 pop ecx ; ecx = 1 = base**0
8048083: ac lods al,BYTE PTR ds:[esi] ; skip the first char so we don't do too many multiplies
; read an input row and accumulate base**n as we go.
08048084 <str_exp.read_bar>:
8048084: 0f af ca imul ecx,edx ; accumulate the exponential
8048087: ac lods al,BYTE PTR ds:[esi]
8048088: 3c 0a cmp al,0xa ; input_separator = newline
804808a: 77 f8 ja 8048084 <str_exp.read_bar>
; AL = separator or terminator
; flags = below (CF=1) or equal (ZF=1). Equal also implies CF=0 in this case.
; store the output row
804808c: b0 30 mov al,0x30 ; output_filler
804808e: f3 aa rep stos BYTE PTR es:[edi],al ; ecx bytes of filler
8048090: 48 dec eax ; mov al,output_separator
8048091: aa stos BYTE PTR es:[edi],al ;append delim
; CF still set from the inner loop, even after DEC clobbers the other flags
8048092: 73 ec jnc 8048080 <str_exp> ; new row if this is a separator, not terminator
8048094: c3 ret
08048095 <end_of_function>
; 0x95 - 0x80 = 0x15 = 21 bytes
Versi 64-bit lebih panjang 1 byte, menggunakan DEC 2-byte atau a mov al, output_separator
. Selain itu, kode mesin sama untuk kedua versi, tetapi beberapa nama register berubah (misalnya rcx
alih-alih ecx
dalam pop
).
Sampel keluaran dari menjalankan program pengujian (basis 3):
$ ./string-exponential $'.\n..\n...\n....' $(seq 3);echo
000/000000000/000000000000000000000000000/000000000000000000000000000000000000000000000000000000000000000000000000000000000/
Algoritma :
Ulangi input, lakukan exp *= base
untuk setiap pengisi char. Pada pembatas dan terminasi nol byte, tambahkan exp
byte filler dan kemudian pemisah ke string output dan reset ke exp=1
. Sangat nyaman bahwa input dijamin tidak berakhir dengan baris baru dan terminator.
Pada input, nilai byte apa pun di atas separator (perbandingan tidak bertanda) diperlakukan sebagai pengisi, dan nilai byte apa pun di bawah separator diperlakukan sebagai penanda akhir string. (Memeriksa secara eksplisit untuk nol-byte akan mengambil tambahan test al,al
vs bercabang pada bendera yang ditetapkan oleh loop dalam).
Aturan hanya memungkinkan pemisah trailing ketika itu adalah baris tambahan. Implementasi saya selalu menambahkan pemisah. Untuk mendapatkan penghematan 1B dalam mode 32-bit, aturan itu memerlukan separator = 0xa ( '\n'
ASCII LF = linefeed), filler = 0xb ( '\v'
ASCII VT = tab vertikal). Itu tidak ramah terhadap manusia, tetapi memenuhi surat hukum. (Anda dapat hexdump atau
tr $'\v' x
output untuk memverifikasi bahwa itu berfungsi, atau mengubah konstanta sehingga pemisah dan pengisi keluaran dapat dicetak. Saya juga memperhatikan bahwa aturan tampaknya mengharuskan dapat menerima input dengan isi yang sama / sep digunakan untuk output , tapi saya tidak melihat keuntungan apa pun dari melanggar aturan itu.).
Sumber NASM / YASM. Bangun sebagai kode 32 atau 64-bit, menggunakan %if
hal - hal yang termasuk dalam program pengujian atau ubah saja rcx ke ecx.
input_separator equ 0xa ; `\n` in NASM syntax, but YASM doesn't do C-style escapes
output_filler equ '0' ; For strict rules-compliance, needs to be input_separator+1
output_separator equ output_filler-1 ; saves 1B in 32-bit vs. an arbitrary choice
;; Using output_filler+1 is also possible, but isn't compatible with using the same filler and separator for input and output.
global str_exp
str_exp: ; void str_exp(char *out /*rdi*/, const char *src /*rsi*/,
; unsigned base /*edx*/);
.new_row:
push 1
pop rcx ; ecx=1 = base**0
lodsb ; Skip the first char, since we multiply for the separator
.read_bar:
imul ecx, edx ; accumulate the exponential
lodsb
cmp al, input_separator
ja .read_bar ; anything > separator is treated as filler
; AL = separator or terminator
; flags = below (CF=1) or equal (ZF=1). Equal also implies CF=0, since x-x doesn't produce carry.
mov al, output_filler
rep stosb ; append ecx bytes of filler to the output string
%if output_separator == output_filler-1
dec eax ; saves 1B in the 32-bit version. Use dec even in 64-bit for easier testing
%else
mov al, output_separator
%endif
stosb ; append the delimiter
; CF is still set from the .read_bar loop, even if DEC clobbered the other flags
; JNC/JNB here is equivalent to JE on the original flags, because we can only be here if the char was below-or-equal the separator
jnc .new_row ; separator means more rows, else it's a terminator
; (f+s)+f+ full-match guarantees that the input doesn't end with separator + terminator
ret
Fungsi mengikuti System86 ABI x86-64, dengan tanda tangan. Fungsi
void str_exp(char *out /*rdi*/, const char *src /*rsi*/, unsigned base /*edx*/);
ini hanya memberi tahu penelepon tentang panjang string keluaran dengan meninggalkan penunjuk satu-melewati-akhir ke dalamnya rdi
, sehingga Anda dapat mempertimbangkan ini sebagai nilai pengembalian dalam Konvensi panggilan standar.
Biayanya 1 atau 2 byte ( xchg eax,edi
) untuk mengembalikan penunjuk akhir dalam eax atau rax. (Jika menggunakan ABI x32, pointer dijamin hanya 32 bit, kalau tidak kita harus menggunakan xchg rax,rdi
jika penelepon melewati pointer ke buffer di luar bit 32 rendah.) Saya tidak memasukkan ini dalam versi saya memposting karena ada solusi yang dapat digunakan pemanggil tanpa mendapatkan nilai dari rdi
, jadi Anda dapat memanggilnya dari C tanpa bungkus.
Kami bahkan tidak menghentikan null string output atau apa pun, jadi itu hanya diakhiri baris baru. Butuh 2 byte untuk memperbaikinya: xchg eax,ecx / stosb
(rcx nol dari rep stosb
.)
Cara untuk mengetahui panjang string output adalah:
- rdi menunjuk ke one-past-the-end dari string on return (sehingga penelepon dapat melakukan len = end-start)
- penelepon hanya bisa tahu berapa banyak baris dalam input dan menghitung baris baru
- penelepon dapat menggunakan buffer zeroed besar dan
strlen()
sesudahnya.
Mereka tidak cantik atau efisien (kecuali untuk menggunakan nilai pengembalian RDI dari pemanggil asm), tetapi jika Anda menginginkannya, jangan panggil fungsi asm golf dari C.: P
Batasan ukuran / rentang
Ukuran string output maksimal hanya dibatasi oleh batasan ruang alamat memori virtual. (Terutama perangkat keras x86-64 saat ini hanya mendukung 48 bit signifikan dalam alamat virtual, terbelah dua karena mereka menandatangani-perluasan alih-alih-nol. Lihat diagram dalam jawaban yang ditautkan .)
Setiap baris hanya dapat memiliki maksimum 2 ** 32 - 1 byte filler, karena saya mengumpulkan eksponensial dalam register 32-bit.
Fungsi ini berfungsi dengan benar untuk basis dari 0 hingga 2 ** 32 - 1. (Benar untuk basis 0 adalah 0 ^ x = 0, yaitu hanya baris kosong tanpa byte filler. Yang benar untuk basis 1 adalah 1 ^ x = 1, jadi selalu 1 pengisi per baris.)
Ini juga sangat cepat pada Intel IvyBridge dan kemudian, terutama untuk baris besar yang ditulis untuk menyelaraskan memori. rep stosb
adalah implementasi optimal memset()
untuk jumlah besar dengan pointer sejajar pada CPU dengan fitur ERMSB . misal 180 ** 4 adalah 0.97GB, dan membutuhkan 0,27 detik pada Skylake i7-6700k saya (dengan ~ 256k kesalahan halaman lunak) untuk menulis ke / dev / null. (Di Linux driver perangkat untuk / dev / null tidak menyalin data di mana pun, itu hanya kembali. Jadi semua waktu berada di rep stosb
dan kesalahan halaman lunak yang dipicu saat menyentuh memori untuk pertama kalinya. Ini sayangnya tidak menggunakan hugepage transparan untuk array di BSS. Mungkin madvise()
panggilan sistem akan mempercepatnya.)
Program uji :
Bangun biner statis dan jalankan sebagai ./string-exponential $'#\n##\n###' $(seq 2)
basis 2. Untuk menghindari penerapannya atoi
, ia menggunakan base = argc-2
. (Batas panjang baris perintah mencegah pengujian basis yang sangat besar.)
Pembungkus ini berfungsi untuk string keluaran hingga 1 GB. (Ini hanya membuat panggilan tunggal () system call bahkan untuk string raksasa, tetapi Linux mendukung ini bahkan untuk menulis ke pipa). Untuk menghitung karakter, masukkan wc -c
atau gunakan strace ./foo ... > /dev/null
untuk melihat arg ke syscall write.
Ini mengambil keuntungan dari nilai pengembalian RDI untuk menghitung panjang string sebagai argumen untuk write()
.
;;; Test program that calls it
;;; Assembles correctly for either x86-64 or i386, using the following %if stuff.
;;; This block of macro-stuff also lets us build the function itself as 32 or 64-bit with no source changes.
%ifidn __OUTPUT_FORMAT__, elf64
%define CPUMODE 64
%define STACKWIDTH 8 ; push / pop 8 bytes
%define PTRWIDTH 8
%elifidn __OUTPUT_FORMAT__, elfx32
%define CPUMODE 64
%define STACKWIDTH 8 ; push / pop 8 bytes
%define PTRWIDTH 4
%else
%define CPUMODE 32
%define STACKWIDTH 4 ; push / pop 4 bytes
%define PTRWIDTH 4
%define rcx ecx ; Use the 32-bit names everywhere, even in addressing modes and push/pop, for 32-bit code
%define rsi esi
%define rdi edi
%define rsp esp
%endif
global _start
_start:
mov rsi, [rsp+PTRWIDTH + PTRWIDTH*1] ; rsi = argv[1]
mov edx, [rsp] ; base = argc
sub edx, 2 ; base = argc-2 (so it's possible to test base=0 and base=1, and so ./foo $'xxx\nxx\nx' $(seq 2) has the actual base in the arg to seq)
mov edi, outbuf ; output buffer. static data is in the low 2G of address space, so 32-bit mov is fine. This part isn't golfed, though
call str_exp ; str_exp(outbuf, argv[1], argc-2)
; leaves RDI pointing to one-past-the-end of the string
mov esi, outbuf
mov edx, edi
sub edx, esi ; length = end - start
%if CPUMODE == 64 ; use the x86-64 ABI
mov edi, 1 ; fd=1 (stdout)
mov eax, 1 ; SYS_write (Linux x86-64 ABI, from /usr/include/asm/unistd_64.h)
syscall ; write(1, outbuf, length);
xor edi,edi
mov eax,231 ; exit_group(0)
syscall
%else ; Use the i386 32-bit ABI (with legacy int 0x80 instead of sysenter for convenience)
mov ebx, 1
mov eax, 4 ; SYS_write (Linux i386 ABI, from /usr/include/asm/unistd_32.h)
mov ecx, esi ; outbuf
; 3rd arg goes in edx for both ABIs, conveniently enough
int 0x80 ; write(1, outbuf, length)
xor ebx,ebx
mov eax, 1
int 0x80 ; 32-bit ABI _exit(0)
%endif
section .bss
align 2*1024*1024 ; hugepage alignment (32-bit uses 4M hugepages, but whatever)
outbuf: resb 1024*1024*1024 * 1
; 2GB of code+data is the limit for the default 64-bit code model.
; But with -m32, a 2GB bss doesn't get mapped, so we segfault. 1GB is plenty anyway.
Ini adalah tantangan yang menyenangkan yang meminjamkan dirinya dengan sangat baik untuk asm, terutama x86 string ops . Aturan dirancang dengan baik untuk menghindari keharusan menangani baris baru dan kemudian terminator di akhir string input.
Eksponensial dengan perkalian berulang sama seperti mengalikan dengan penambahan berulang, dan saya perlu mengulang untuk menghitung karakter di setiap baris input.
Saya mempertimbangkan untuk menggunakan satu operan mul
atau imul
lebih lama imul r,r
, tetapi penggunaan EAX secara implisit akan bertentangan dengan LODSB.
Saya juga mencoba SCASB daripada memuat dan membandingkan , tetapi saya perlu xchg esi,edi
sebelum dan sesudah loop dalam, karena SCASB dan STOSB keduanya menggunakan EDI. (Jadi versi 64-bit harus menggunakan ABI x32 untuk menghindari pemotongan pointer 64-bit).
Menghindari STOSB bukanlah suatu pilihan; tidak ada yang sedekat ini. Dan setengah keuntungan menggunakan SCASB adalah AL = filler setelah meninggalkan loop dalam, jadi kita tidak memerlukan pengaturan untuk REP STOSB.
SCASB membandingkan ke arah lain dari apa yang telah saya lakukan, jadi saya perlu membalikkan perbandingan.
Upaya terbaik saya dengan xchg dan scasb. Bekerja, tetapi tidak lebih pendek. ( Kode 32-bit, menggunakaninc
/ dec
trik untuk mengubah filler menjadi separator ).
; SCASB version, 24 bytes. Also experimenting with a different loop structure for the inner loop, but all these ideas are break-even at best
; Using separator = filler+1 instead of filler-1 was necessary to distinguish separator from terminator from just CF.
input_filler equ '.' ; bytes below this -> terminator. Bytes above this -> separator
output_filler equ input_filler ; implicit
output_separator equ input_filler+1 ; ('/') implicit
8048080: 89 d1 mov ecx,edx ; ecx=base**1
8048082: b0 2e mov al,0x2e ; input_filler= .
8048084: 87 fe xchg esi,edi
8048086: ae scas al,BYTE PTR es:[edi]
08048087 <str_exp.read_bar>:
8048087: ae scas al,BYTE PTR es:[edi]
8048088: 75 05 jne 804808f <str_exp.bar_end>
804808a: 0f af ca imul ecx,edx ; exit the loop before multiplying for non-filler
804808d: eb f8 jmp 8048087 <str_exp.read_bar> ; The other loop structure (ending with the conditional) would work with SCASB, too. Just showing this for variety.
0804808f <str_exp.bar_end>:
; flags = below if CF=1 (filler<separator), above if CF=0 (filler<terminator)
; (CF=0 is the AE condition, but we can't be here on equal)
; So CF is enough info to distinguish separator from terminator if we clobber ZF with INC
; AL = input_filler = output_filler
804808f: 87 fe xchg esi,edi
8048091: f3 aa rep stos BYTE PTR es:[edi],al
8048093: 40 inc eax ; output_separator
8048094: aa stos BYTE PTR es:[edi],al
8048095: 72 e9 jc 8048080 <str_exp> ; CF is still set from the inner loop
8048097: c3 ret
Untuk input ../.../.
, hasilkan ..../......../../
. Saya tidak akan repot menunjukkan hexdump versi dengan separator = newline.
"" <> "#"~Table~#
adalah 3 byte lebih pendek dari"#"~StringRepeat~#
, mungkin golf juga lebih jauh.Japt , 7 byte
Mengambil grafik sebagai array string dengan
"
sebagai filler, dan basis sebagai integer.Cobalah online
Tambahkan
}R
ke akhir untuk mengambil grafik sebagai string yang dipisahkan baris baru. ( Cobalah )Penjelasan
sumber
MATL ,
1411 bytePembatas adalah ruang. Filler adalah karakter apa pun selain ruang.
Cobalah online!
Penjelasan
sumber
Haskell ,
3733 byte4 byte dicukur berkat sudee
Deskripsi:
Yang mengecewakan, ini
2 bytelebih pendek dari versi pointfree cara-sulit dibaca:sumber
replicate(b^length x)'#'
dengan'#'<$[1..b^length x]
.ReRegex , 105 byte
Cobalah online!
ReRegex seperti sepupu jelek Retina yang memberikan semua upaya untuk Ekspresi Reguler, daripada memiliki operator mewahnya sendiri.
Tentu saja, ia juga memiliki
#import
dan#input
menyimpan input hardcoding, dan menulis ulang ekspresi yang sama berulang-ulang.Dijelaskan.
Mengambil input dalam bentuk:
pada STDIN, dan memberikan output seperti
Pertama, program ini mengimpor Perpustakaan Matematika , yang tentu saja sepenuhnya ditulis dalam ReRegex. Bagian terbesar dari ini adalah tiga ekspresi reguler.
Yang pertama cocok dengan basis input kami, dan mencari garis unary setelahnya. kemudian, ganti baris itu dengan
;$1^d<$4>
, yang merupakan dasar, dengan kekuatan Unimal (Dalam Desimal). Perpustakaan Math menangani konversi basis dan eksponen. SEBUAH ; ditempatkan di awal untuk mengidentifikasi nanti setelah selesai.Yang kedua, cocok dengan basis, lalu banyak baris;, sebelum berakhir. Jika ini cocok dengan semuanya, ia akan terlepas dari pangkalan. meninggalkan uf hanya dengan jawaban dan
;
s.Yang terakhir, cocok hanya unary di awal, secara opsional, lalu
;
jawaban. Kemudian mengubah jawaban itu menjadi unary lagi, tanpa;
.Karena output tidak cocok dengan regex pertama, itu tidak berulang, jadi solusi kami dikeluarkan.
sumber
Python 2 ,
5236 byteInput dan output diambil sebagai array string.
#
adalah pengisi.Cobalah online!
sumber
Röda , 19 byte
Cobalah online!
Mengambil array sebagai input dan mengembalikan aliran nilai sebagai output.
Penjelasan
sumber
Haskell , 32 byte
Cobalah online! Contoh penggunaan:
f 3 ["##","#","###","#"]
pengembalian["#########","###","###########################","###"]
.Gunakan
mapM putStrLn $ f 3 ["##","#","###","#"]
untuk mendapatkan hasil yang lebih menyenangkan secara visual:sumber
sum[sum[]^sum[],sum[]^sum[]]
.05AB1E , 9 byte
Bar dipisahkan oleh spasi, karakter output sama dengan karakter input.
Cobalah online!
sumber
PHP, 69 Bytes
Cobalah online!
sumber
[str_pad]."\n"
alih-alih"\n".[str_pad]
memperbaiki ini (+1 byte). Selain itu, Anda dapat mengasumsikan pengisi apa, sehingga Anda dapat menyimpan dua byte$l[0]
dengan mengubahnya"#"
.Jelly , 7 byte
Tautan monadik yang mengambil dan mengembalikan daftar bilah (daftar karakter itu sendiri, string AKA) karakter pengisi fleksibel.
Cobalah online!(footer menyiapkan daftar hasil dengan menggabungkan elemen-elemennya dengan baris baru.)
Bagaimana?
Alternatif 7-byter:
ṁ"L€*@¥
- dapatkan panjang masing-masing bar (L€
), naikkanbase
ke kekuatan itu (*@
), lalu zip ("
) daftar dan yang menerapkan angka dua cetakan (ṁ
) di antara keduanya.sumber
Ruby , 29 byte
Cobalah online!
Ya, saya menemukan minggu lalu yang
?#
menghasilkan string karakter tunggal. Saya tidak tahu mengapa fitur ini ada, tapi saya senang itu.sumber
?X
operator, di manaX
beberapa karakter, adalah "mendapatkan representasi default karakter ini" operator. Di Ruby <1.9, itu akan mengembalikan titik kode Unicode karakter, karena itulah cara karakter didefinisikan, tetapi sekarang mengembalikan string yang berisi karakter. Ini adalah bagian dari perubahan umum menuju penanganan Unicode yang lebih konsisten di Ruby.?X
digunakan? Banyak konvensi Ruby yang unik, seperti kebanyakan$
-variables, ada karena keakraban dengan Perl.JavaScript (ES8), 39 byte
Mengambil basis sebagai integer dan grafik sebagai array string dengan karakter apa pun sebagai pengisi, menggunakan sintaks currying.
Cobalah
Alternatif, 49 byte
Versi ini mengambil grafik sebagai string yang dipisahkan baris baru, lagi dengan karakter apa pun sebagai pengisi.
sumber
m
bendera di regex, secara default.
tidak cocok dengan baris baru.Mathematica, 86 byte
memasukkan
sumber
Oktaf, 42 byte
* String input / output tidak sepenuhnya cocok dengan regex tetapi dimungkinkan untuk memahami bilah mana yang mana.
Fungsi diambil sebagai basis input
b
dan array 2D yangs
berisi karakter"!"
dan output juga merupakan array karakter.Cobalah online!
Penjelasan:
sumber
CJam, 20 byte
Masukkan format
Input diperlukan dalam format berikut:
sumber
Arang , 11 byte
Cobalah online! Tautan adalah untuk mengucapkan versi kode. I / O adalah sebagai daftar string
-
karakter (perhatikan bahwa Anda memerlukan baris kosong untuk mengakhiri daftar).sumber
V , 27 byte
Ide dasarnya adalah bahwa kita menambahkan a
'
ke setiap baris (n ^ 0), dan kemudian untuk masing-masing#
kita mengganti'
s di baris dengan[input] * '
. Pada akhirnya saya bertukar semua'
untuk#
lagiCobalah online!
sumber
R , 35 byte
fungsi anonim yang mengambil string sebagai daftar dan basis, dan mengembalikan daftar string.
Cobalah online!
sumber
05AB1E , 10 byte
Karakter filer adalah
1
dan pembatas adalah baris baru.Cobalah online!
sumber
Retina , 62 byte
Cobalah online! Bagaimanapun, grafik batang hanyalah daftar angka-angka yang tidak diperhatikan. Mengambil input sebagai grafik (menggunakan
#
s) diikuti oleh basis dalam desimal (untuk menghindari kebingungan). Penjelasan: Awalan pengganti pertama 1 dan dasar untuk setiap baris grafik. Penggantian kedua kemudian mengalikan angka pertama pada setiap baris dengan yang kedua, selama angka ketiga bukan nol. Penggantian ketiga kemudian menurunkan angka ketiga di setiap baris. Kedua penggantian ini diulangi sampai angka ketiga menjadi nol. Penggantian terakhir menghapus basis di mana-mana, meninggalkan hasil yang diinginkan.sumber
Cembung , 9 byte
Cobalah online!
sumber
Alice , 23 byte
Cobalah online!
Bukan saja saya bukan orang yang gampang menyerah, tetapi saya juga berkomitmen untuk membuat poin dengan tepat yang saya gunakan
!
sebagai pengisi. Itu pasti akan mendapat perhatian pembaca.Penjelasan
Cermin dipertahankan dalam penjelasan ini untuk membuatnya lebih jelas ketika program beralih antara mode kardinal dan ordinal.
sumber
Perl 6 , 26 byte
Daftar string input ada di parameter pertama
@^a
,. Parameter kedua$^b
adalah basis. Daftar string keluaran dikembalikan.sumber