Log Scales are for Quitters Everyone knows log scales are for quitters. Therefore, you must write a program or function that de-quitifies a bar graph with a log scale given a base. 

The bar graph input is taken as a single string which is a list of bars, where each bar of the log scale bar graph is separated by the printable (or whitespace) delimiter of your choosing (so 0x09-0x0A + 0x20-0x7E) and composed of a printable non-whitespace (so 0x21-0x7E) filler character of your choosing. 

The program or function outputs a single string which is a list of bars, where each bar is separated by the same delimiter the input was separated by and is composed of the same filler character the input was composed of.

Example

We choose a delimiter of "\n" (one newline) and a filler character of "#".
The input passed to our program or function is:

base=2
and
string=

####
##
######
###


The code would find that the lengths of the bars are [4,2,6,3]. It would compute the anti-log of each length with base 2 to get [2^4,2^2,2^6,2^3] = [16,4,64,8]. Then, the lengths are output in linear scale bar format:

################
####
################################################################
########


Input / Output

Your program or function may input and output in any reasonable format.

The input base is guaranteed to be an integer greater than 1. You may assume the base is less than 256.
The string input is guaranteed to fully match the regex (f+s)+f+, where f and s are replaced with your filler and delimiter respectively.

The string output must fully match the regex (f+s)+f+, where f and s are replaced with the same filler and delimiter respectively. The output may optionally have a trailing newline.

The output and input may also be a list of strings instead of delimited by a substring, though it must be possible to understand which bar is which.

Testcases

(assume filler is # and delimiter is \n)

base
-
input string
-
output string
-----
2
-
####
##
######
###
-
################
####
################################################################
########
-----
3
-
##
#
###
#
-
#########
###
###########################
###
-----
100
-
#   I am not the delimiter
###  nor the filler
-
Anything (You do not have to handle input which does not match the regex)
-----
1
-
###
#######
###################################################
- 
Anything (You do not have to handle bases less than or equal to 1).
-----
5
-
####
##
###
#
-
#################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################################    
#########################
#############################################################################################################################
#####
-----
2
-
#
#
##
##
#
##
#
#
#
#
##
##
#
#
##
#
-
##
##
####
####
##
####
##
##
##
##
####
####
##
##
####
##
x86 32-bit machine code function, 21 bytes

x86-64 machine code function, 22 bytes

The 1B saving in 32-bit mode requires using separator = filler-1, e.g. fill=0 and sep=/.  The 22-byte version can use an arbitrary choice of separator and filler.



This is the 21-byte version, with input-separator = \n (0xa), output-filler = 0, output-separator = / = filler-1.  These constants can be easily changed.

; 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 &lt;str_exp&gt;:
 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 &lt;str_exp.read_bar&gt;:
 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 &lt;str_exp.read_bar&gt;
 ; 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 &lt;str_exp&gt;  ; new row if this is a separator, not terminator

 8048094:       c3              ret    

08048095  &lt;end_of_function&gt;
; 0x95 - 0x80 = 0x15 = 21 bytes


The 64-bit version is 1 byte longer, using a 2-byte DEC or a mov al, output_separator.  Other than that, the machine-code is the same for both versions, but some register names change (e.g. rcx instead of ecx in the pop).

Sample output from running the test program (base 3):

$ ./string-exponential $'.\n..\n...\n....' $(seq 3);echo 
000/000000000/000000000000000000000000000/000000000000000000000000000000000000000000000000000000000000000000000000000000000/


Algorithm:

Loop over the input, doing exp *= base for every filler char.  On delimiters and the terminating zero byte, append exp bytes of filler and then a separator to the output string and reset to exp=1.  It's very convenient that the input is guaranteed not to end with both a newline and a terminator.

On input, any byte value above the separator (unsigned compare) is treated as filler, and any byte value below the separator is treated as an end-of-string marker.  (Checking explicitly for a zero-byte would take an extra test al,al vs. branching on flags set by the inner loop).



The rules only allow a trailing separator when it's a trailing newline.  My implementation always appends the separator.  To get the 1B saving in 32-bit mode, that rule requires separator = 0xa ('\n' ASCII LF = linefeed), filler = 0xb ('\v' ASCII VT = vertical tab).  That's not very human-friendly, but satisfies the letter of the law.  (You can hexdump or
tr $'\v' x the output to verify that it works, or change the constant so the output separator and filler are printable.  I also noticed that the rules seem to require that it can accept input with the same fill/sep it uses for output, but I don't see anything to gain from breaking that rule.).



NASM/YASM source.  Build as 32 or 64-bit code, using the %if stuff included with the test program or just change rcx to 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 &gt; 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


The function follows the x86-64 SystemV ABI, with signature
void str_exp(char *out /*rdi*/, const char *src /*rsi*/, unsigned base /*edx*/);
It only informs the caller of the length of the output string by leaving a one-past-the-end pointer to it in rdi, so you could consider this the return value in a non-standard calling convention.

It would cost 1 or 2 bytes (xchg eax,edi) to return the end-pointer in eax or rax.  (If using the x32 ABI, pointers are guaranteed to be only 32 bits, otherwise we have to use xchg rax,rdi in case the caller passes a pointer to a buffer outside the low 32 bits.)  I didn't include this in the version I'm posting because there are workarounds the caller can use without getting the value from rdi, so you could call this from C with no wrapper.  

We don't even null-terminate the output string or anything, so it's only newline-terminated.  It would take 2 bytes to fix that: xchg eax,ecx / stosb  (rcx is zero from rep stosb.)

The ways to find out the output-string length are:


rdi points to one-past-the-end of the string on return (so the caller can do len=end-start)
the caller can just know how many rows were in the input and count newlines
the caller can use a large zeroed buffer and strlen() afterwards.


They're not pretty or efficient (except for using the RDI return value from an asm caller), but if you want that then don't call golfed asm functions from C. :P



Size/range limitations

The max output string size is only limited by virtual memory address-space limitations.  (Mainly that current x86-64 hardware only supports 48 significant bits in virtual addresses, split in half because they sign-extend instead of zero-extend.  See the diagram in the linked answer.)

Each row can only have a maximum of 2**32 - 1 filler bytes, since I accumulate the exponential in a 32-bit register.

The function works correctly for bases from 0 to 2**32 - 1.  (Correct for base 0 is 0^x = 0, i.e. just blank lines with no filler bytes.  Correct for base 1 is 1^x = 1, so always 1 filler per line.)

It's also blazingly fast on Intel IvyBridge and later, especially for large rows being written to aligned memory.  rep stosb is an optimal implementation of memset() for large counts with aligned pointers on CPUs with the ERMSB feature.  e.g. 180**4 is 0.97GB, and takes 0.27 seconds on my i7-6700k Skylake (with ~256k soft page-faults) to write to /dev/null.  (On Linux the device-driver for /dev/null doesn't copy the data anywhere, it just returns.  So all of the time is in the rep stosb and the soft page-faults that triggers when touching the memory for the first time.  It's unfortunately not using transparent hugepages for the array in the BSS.  Probably an madvise() system call would speed it up.)

Test program:

Build a static binary and run as ./string-exponential $'#\n##\n###' $(seq 2) for base 2.  To avoid implementing an atoi, it uses base = argc-2.  (Command-line length limits prevent testing ridiculously large bases.)

This wrapper works for output strings up to 1 GB.  (It only makes a single write() system call even for gigantic strings, but Linux supports this even for writing to pipes).  For counting characters, either pipe into wc -c or use strace ./foo ... &gt; /dev/null to see the arg to the write syscall.

This takes advantage of the RDI return-value to calculate the string length as an arg for 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.




This was a fun challenge that lent itself very well to asm, especially x86 string ops.  The rules are nicely designed to avoid having to handle a newline and then a terminator at the end of the input string.

An exponential with repeated multiplication is just like multiplying with repeated addition, and I needed to loop to count chars in each input row anyway.

I considered using one-operand mul or imul instead of the longer imul r,r, but its implicit use of EAX would conflict with LODSB.



I also tried SCASB instead of load and compare, but I needed xchg esi,edi before and after the inner loop, because SCASB and STOSB both use EDI.  (So the 64-bit version has to use the x32 ABI to avoid truncating 64-bit pointers).

Avoiding STOSB is not an option; nothing else is anywhere near as short.  And half the benefit of using SCASB is that AL=filler after leaving the inner loop, so we don't need any setup for REP STOSB.

SCASB compares in the other direction from what I had been doing, so I needed to reverse the comparisons.

My best attempt with xchg and scasb.  Works, but isn't shorter.  (32-bit code, using the inc/dec trick to change filler into 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 -&gt; terminator.  Bytes above this -&gt; 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 &lt;str_exp.read_bar&gt;:
 8048087:       ae                      scas   al,BYTE PTR es:[edi]
 8048088:       75 05                   jne    804808f &lt;str_exp.bar_end&gt;
 804808a:       0f af ca                imul   ecx,edx           ; exit the loop before multiplying for non-filler
 804808d:       eb f8                   jmp    8048087 &lt;str_exp.read_bar&gt;   ; The other loop structure (ending with the conditional) would work with SCASB, too.  Just showing this for variety.
0804808f &lt;str_exp.bar_end&gt;:

; flags = below if CF=1 (filler&lt;separator),  above if CF=0 (filler&lt;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 &lt;str_exp&gt;   ; CF is still set from the inner loop
 8048097:       c3                      ret    


For an input of ../.../., produces ..../......../../.  I'm not going to bother showing a hexdump of the version with separator=newline.