[Question]
  [
Suppose we use the following rules to pull a single string from another string, one containing only ASCII printable characters and called an `*`-string. If the string runs out before the process halts, that is an error, and the result of the process is undefined in that case:
1. Start with `d=1, s=""`
2. Whenever you encounter a `*`, multiply `d` by 2. Whenever you encounter another character, concatenate it to the end of `s` and subtract 1 from `d`. If now `d=0`, halt and return `s`
**Defined Examples**:
```
d->d
769->7
abcd56->a
*abcd56->ab
**abcd56->abcd
*7*690->769
***abcdefghij->abcdefgh
```
**Undefined Examples**: (note that the empty string would be one of these as well)
```
*7
**769
*7*
*a*b
*
```
Your job is to take a string and return the shortest `*`-string that produces that string.
**Program Examples**:
```
7->7
a->a
ab->*ab
abcd->**abcd
769->*7*69
```
Your program should handle any string containing at least one character and only non-`*` ASCII printable characters. You can never return strings for which the process is undefined, since by definition they cannot produce ANY strings.
Standard loopholes and I/O rules apply.
  
[Answer]
# JavaScript (ES6), 61 bytes
```
f=(s,d=2)=>s?d>s.length?s[0]+f(s.slice(1),d-2):'*'+f(s,d*2):s
```
Recursive function that does the following:
* If `d` is less than or equal to remaining string length divided by 2:
Append `*` to output and multiply `d` by 2
* Else:
Shift the string and append to output, subtract 1 from `d`.
See it in action:
```
f=(s,d=2)=>s?d>s.length?s[0]+f(s.slice(1),d-2):'*'+f(s,d*2):s
input.oninput = e => output.innerHTML = f(input.value);
```
```
<input id="input" type="text"/>
<p id="output"></p>
```
[Answer]
## Pyth, ~~29~~ ~~27~~ (Noticed broken) ~~27~~ ~~26~~ 25 bytes
```
+*\*sKllzXJ-^2.EKlzz?J\*k
```
Explanation to come.
[Test Suite](http://pyth.herokuapp.com/?code=%2B%2a%5C%2asKllzXJ-%5E2.EKlzz%3FJ%5C%2ak&input=a%0Aab%0Aabc%0Aabcd%0Aabcde%0Aabcdef%0Aabcdefg%0Aabcdefgh&test_suite=1&test_suite_input=a%0Aab%0Aabc%0Aabcd%0Aabcde%0Aabcdef%0Aabcdefg%0Aabcdefgh&debug=0)
[Answer]
# Pyth (36 27 bytes)
Thanks to Jakube for a 9 byte improvement!
Currently not as good as [muddyfish's answer](https://codegolf.stackexchange.com/a/75912/52152), but whatever
```
KlzJ1VzWgKyJp\*=yJ)pN=tK=tJ
```
[Test Suite](https://pyth.herokuapp.com/?code=KlzJ1VzWgKyJp%5C*%3DyJ%29pN%3DtK%3DtJ&input=goodbye&test_suite=1&test_suite_input=769%0AHello+World!%0Aabcd%0AThis+answer+is+pretty+good+now!%0AThank+you+Jakube!&debug=0)
Translation to python:
```
                            | z=input() #occurs by default
Klz                         | K=len(z)
   J1                       | J=1
     Vz                     | for N in z:
       WgKyJ                |   while K >= J*2:
            p\*             |     print("*", end="")
               =yJ          |     J=J*2
                  )         |     #end inside while
                   pN       |   print(N, end="")
                     =tK    |   K=K-1
                        =tJ |   J=J-1
```
[Answer]
## C, 125 bytes
```
main(int q,char**v){++v;int i=1,n=strlen(*v);while(n>(i*=2))putchar(42);for(i-=n;**v;--i,++*v)!i&&putchar(42),putchar(**v);}
```
This takes advantage of the very regular pattern of star positions to output the correct encoding. Initially I tried a bruteforce recursive solution, but in retrospect it should have been obvious that there was a simpler mathematical solution.
Essentially you will always have `2^floor(log_2(length))` stars at the start of your output, and a final star after `2^ceil(log_2(length)) - length` characters (if that works out to at least 1 character).
The (slightly) ungolfed version is as follows
```
main(int q,char**v){
   ++v;                         // refer to the first command line argument
   int i=1, n=strlen(*v);       // set up iteration variables
   
   while(n > (i*=2))            // print the first floor(log2(n)) '*'s
      putchar(42);
   
   for(i-=n;  **v;  --i, ++*v)  // print the string, and the final '*'
      !i&&putchar(42),putchar(**v);
}
```
[Answer]
## JavaScript (ES6), ~~88~~ 77 bytes
```
f=(s,l=s.length,p=2)=>l<2?s:p<l?"*"+f(s,l,p*2):s.slice(0,p-=l)+"*"+s.slice(p)
```
At first I thought that `abcde` had to be `*a**bcde` but it turns out that `**abc*de` works just as well. This means that the output is readily constructed using floor(log₂(s.length)) leading stars, plus an additional star for strings whose length is not a power of two.
Edit: Saved 8 bytes by calculating the number of leading stars recursively. Saved a further 3 bytes by special-casing strings of length 1, so that I can treat strings whose length is a power of 2 as having an extra leading star.
[Answer]
**Haskell, 68 bytes**
```
f d[]=""
f d xs|length xs>=d*2='*':f(d*2)xs
f d(x:xs)=x:f(d-1)xs
```
Same as the other answers, really. If EOF, output an empty string. If length remaining is more than twice `d`, output a star and double `d`. Otherwise, output the next character and subtract one from `d`.
Ungolfed:
```
f d (  [])                    = ""
f d (  xs) | length xs >= d*2 = '*' : f (d*2) xs
f d (x:xs)                    =  x  : f (d-1) xs
```
[Answer]
# [Ruby](https://www.ruby-lang.org/), 58 bytes
```
F=->a,s="",d=1{x,*y=a
d<1?s:x==?*?F[y,s,d*2]:F[y,s+x,d-1]}
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m72kqDSpcsGCpaUlaboWN63cbHXtEnWKbZWUdFJsDasrdLQqbRO5UmwM7YutKmxt7bXs3aIrdYp1UrSMYq3ATO0KnRRdw9haiAm3GP0KSkuKFdyiVcujU2JjFXACZQVdO4UULoRqcwUzBUtcOsCqzZFUJyokKSQrpCiYKphh6gGrTkRSraWARz1EdRKKcjwaoMqTU1A0mAO1AN2vYIDDNeZmlmgWIKxIVUhTSFfIUMhUyALphluQmpaeAQlWWAQBAA)
]