This notebook contains the code samples found in Chapter 8, Section 1 of Deep Learning with R. Note that the original text features far more content, in particular further explanations and figures: in this notebook, you will only find source code and related comments.


Implementing character-level LSTM text generation

Let’s put these ideas in practice in a Keras implementation. The first thing we need is a lot of text data that we can use to learn a language model. You could use any sufficiently large text file or set of text files – Wikipedia, the Lord of the Rings, etc. In this example we will use some of the writings of Nietzsche, the late-19th century German philosopher (translated to English). The language model we will learn will thus be specifically a model of Nietzsche’s writing style and topics of choice, rather than a more generic model of the English language.

Preparing the data

Let’s start by downloading the corpus and converting it to lowercase:

library(keras)
library(stringr)
path <- get_file(
  "nietzsche.txt",
  origin = "https://s3.amazonaws.com/text-datasets/nietzsche.txt"
)
text <- tolower(readChar(path, file.info(path)$size))
cat("Corpus length:", nchar(text), "\n")
Corpus length: 600893 

Next, you’ll extract partially overlapping sequences of length maxlen, one-hot encode them, and pack them in a 3D array x of shape (sequences, maxlen, unique_characters). Simultaneously, you’ll prepare an array y containing the corresponding targets: the one-hot-encoded characters that come after each extracted sequence.

maxlen <- 60  # Length of extracted character sequences
step <- 3  # We sample a new sequence every `step` characters
  
text_indexes <- seq(1, nchar(text) - maxlen, by = step)
# This holds our extracted sequences
sentences <- str_sub(text, text_indexes, text_indexes + maxlen - 1)
# This holds the targets (the follow-up characters)
next_chars <- str_sub(text, text_indexes + maxlen, text_indexes + maxlen)
cat("Number of sequences: ", length(sentences), "\n")
Number of sequences:  200278 
# List of unique characters in the corpus
chars <- unique(sort(strsplit(text, "")[[1]]))
cat("Unique characters:", length(chars), "\n")
Unique characters: 57 
# Dictionary mapping unique characters to their index in `chars`
char_indices <- 1:length(chars) 
names(char_indices) <- chars
# Next, one-hot encode the characters into binary arrays.
cat("Vectorization...\n") 
Vectorization...
x <- array(0L, dim = c(length(sentences), maxlen, length(chars)))
y <- array(0L, dim = c(length(sentences), length(chars)))
for (i in 1:length(sentences)) {
  sentence <- strsplit(sentences[[i]], "")[[1]]
  for (t in 1:length(sentence)) {
    char <- sentence[[t]]
    x[i, t, char_indices[[char]]] <- 1
  }
  next_char <- next_chars[[i]]
  y[i, char_indices[[next_char]]] <- 1
}

Building the network

This network is a single LSTM layer followed by a dense classifier and softmax over all possible characters. But note that recurrent neural networks aren’t the only way to do sequence data generation; 1D convnets also have proven extremely successful at this task in recent times.

model <- keras_model_sequential() %>% 
  layer_lstm(units = 128, input_shape = c(maxlen, length(chars))) %>% 
  layer_dense(units = length(chars), activation = "softmax")

Since our targets are one-hot encoded, we will use categorical_crossentropy as the loss to train the model:

optimizer <- optimizer_rmsprop(lr = 0.01)
model %>% compile(
  loss = "categorical_crossentropy", 
  optimizer = optimizer
)   

Training the language model and sampling from it

Given a trained model and a seed text snippet, we generate new text by repeatedly:

This is the code we use to reweight the original probability distribution coming out of the model, and draw a character index from it (the “sampling function”):

sample_next_char <- function(preds, temperature = 1.0) {
  preds <- as.numeric(preds)
  preds <- log(preds) / temperature
  exp_preds <- exp(preds)
  preds <- exp_preds / sum(exp_preds)
  which.max(t(rmultinom(1, 1, preds)))
}

Finally, the following loop repeatedly trains and generates text. You begin generating text using a range of different temperatures after every epoch. This allows you to see how the generated text evolves as the model begins to converge, as well as the impact of temperature in the sampling strategy.

for (epoch in 1:60) {
  
  cat("epoch", epoch, "\n")
  
  # Fit the model for 1 epoch on the available training data
  model %>% fit(x, y, batch_size = 128, epochs = 1) 
  
  # Select a text seed at random
  start_index <- sample(1:(nchar(text) - maxlen - 1), 1)  
  seed_text <- str_sub(text, start_index, start_index + maxlen - 1)
  
  cat("--- Generating with seed:", seed_text, "\n\n")
  
  for (temperature in c(0.2, 0.5, 1.0, 1.2)) {
    
    cat("------ temperature:", temperature, "\n")
    cat(seed_text, "\n")
    
    generated_text <- seed_text
    
     # We generate 400 characters
    for (i in 1:400) {
      
      sampled <- array(0, dim = c(1, maxlen, length(chars)))
      generated_chars <- strsplit(generated_text, "")[[1]]
      for (t in 1:length(generated_chars)) {
        char <- generated_chars[[t]]
        sampled[1, t, char_indices[[char]]] <- 1
      }
        
      preds <- model %>% predict(sampled, verbose = 0)
      next_index <- sample_next_char(preds[1,], temperature)
      next_char <- chars[[next_index]]
      
      generated_text <- paste0(generated_text, next_char)
      generated_text <- substring(generated_text, 2)
      
      cat(next_char)
    }
    cat("\n\n")
  }
}

Here, we used the random seed text “new faculty, and the jubilation reached its climax when kant.” Here’s what you get at epoch 20, long before the model has fully converged, with temperature=0.2:

new faculty, and the jubilation reached its climax when kant and such a man
in the same time the spirit of the surely and the such the such 
as a man is the sunligh and subject the present to the superiority of the 
special pain the most man and strange the subjection of the 
special conscience the special and nature and such men the subjection of the
special men, the most surely the subjection of the special 
intellect of the subjection of the same things and

Here’s the result with temperature=0.5:

new faculty, and the jubilation reached its climax when kant in the eterned 
and such man as it's also become himself the condition of the 
experience of off the basis the superiory and the special morty of the 
strength, in the langus, as which the same time life and "even who 
discless the mankind, with a subject and fact all you have to be the stand
and lave no comes a troveration of the man and surely the 
conscience the superiority, and when one must be w

And here’s what you get with temperature=1.0:

new faculty, and the jubilation reached its climax when kant, as a 
periliting of manner to all definites and transpects it it so 
hicable and ont him artiar resull
too such as if ever the proping to makes as cnecience. to been juden, 
all every could coldiciousnike hother aw passife, the plies like 
which might thiod was account, indifferent germin, that everythery 
certain destrution, intellect into the deteriorablen origin of moralian, 
and a lessority o

At epoch 60, the model has mostly converged, and the text starts to look significantly more coherent. Here’s the result with temperature=0.2:

cheerfulness, friendliness and kindness of a heart are the sense of the 
spirit is a man with the sense of the sense of the world of the 
self-end and self-concerning the subjection of the strengthorixes--the 
subjection of the subjection of the subjection of the 
self-concerning the feelings in the superiority in the subjection of the 
subjection of the spirit isn't to be a man of the sense of the 
subjection and said to the strength of the sense of the

Here is temperature=0.5:

cheerfulness, friendliness and kindness of a heart are the part of the soul
who have been the art of the philosophers, and which the one 
won't say, which is it the higher the and with religion of the frences. 
the life of the spirit among the most continuess of the 
strengther of the sense the conscience of men of precisely before enough 
presumption, and can mankind, and something the conceptions, the 
subjection of the sense and suffering and the

And here is temperature=1.0:

cheerfulness, friendliness and kindness of a heart are spiritual by the 
ciuture for the
entalled is, he astraged, or errors to our you idstood--and it needs, 
to think by spars to whole the amvives of the newoatly, prefectly 
raals! it was
name, for example but voludd atu-especity"--or rank onee, or even all 
"solett increessic of the world and
implussional tragedy experience, transf, or insiderar,--must hast
if desires of the strubction is be stronges

As you can see, a low temperature results in extremely repetitive and predictable text, but where local structure is highly realistic: in particular, all words (a word being a local pattern of characters) are real English words. With higher temperatures, the generated text becomes more interesting, surprising, even creative; it may sometimes invent completely new words that sound somewhat plausible (such as “eterned” or “troveration”). With a high temperature, the local structure starts breaking down and most words look like semi-random strings of characters. Without a doubt, here 0.5 is the most interesting temperature for text generation in this specific setup. Always experiment with multiple sampling strategies! A clever balance between learned structure and randomness is what makes generation interesting.

Note that by training a bigger model, longer, on more data, you can achieve generated samples that will look much more coherent and realistic than ours. But of course, don’t expect to ever generate any meaningful text, other than by random chance: all we are doing is sampling data from a statistical model of which characters come after which characters. Language is a communication channel, and there is a distinction between what communications are about, and the statistical structure of the messages in which communications are encoded. To evidence this distinction, here is a thought experiment: what if human language did a better job at compressing communications, much like our computers do with most of our digital communications? Then language would be no less meaningful, yet it would lack any intrinsic statistical structure, thus making it impossible to learn a language model like we just did.

Take aways

LS0tCnRpdGxlOiAiVGV4dCBnZW5lcmF0aW9uIHdpdGggTFNUTSIKb3V0cHV0OiAKICBodG1sX25vdGVib29rOiAKICAgIHRoZW1lOiBjZXJ1bGVhbgogICAgaGlnaGxpZ2h0OiB0ZXh0bWF0ZQotLS0KCmBgYHtyIHNldHVwLCBpbmNsdWRlPUZBTFNFfQprbml0cjo6b3B0c19jaHVuayRzZXQod2FybmluZyA9IEZBTFNFLCBtZXNzYWdlID0gRkFMU0UpCmBgYAoKKioqCgpUaGlzIG5vdGVib29rIGNvbnRhaW5zIHRoZSBjb2RlIHNhbXBsZXMgZm91bmQgaW4gQ2hhcHRlciA4LCBTZWN0aW9uIDEgb2YgW0RlZXAgTGVhcm5pbmcgd2l0aCBSXShodHRwczovL3d3dy5tYW5uaW5nLmNvbS9ib29rcy9kZWVwLWxlYXJuaW5nLXdpdGgtcikuIE5vdGUgdGhhdCB0aGUgb3JpZ2luYWwgdGV4dCBmZWF0dXJlcyBmYXIgbW9yZSBjb250ZW50LCBpbiBwYXJ0aWN1bGFyIGZ1cnRoZXIgZXhwbGFuYXRpb25zIGFuZCBmaWd1cmVzOiBpbiB0aGlzIG5vdGVib29rLCB5b3Ugd2lsbCBvbmx5IGZpbmQgc291cmNlIGNvZGUgYW5kIHJlbGF0ZWQgY29tbWVudHMuCgoqKioKCgojIyBJbXBsZW1lbnRpbmcgY2hhcmFjdGVyLWxldmVsIExTVE0gdGV4dCBnZW5lcmF0aW9uCgoKTGV0J3MgcHV0IHRoZXNlIGlkZWFzIGluIHByYWN0aWNlIGluIGEgS2VyYXMgaW1wbGVtZW50YXRpb24uIFRoZSBmaXJzdCB0aGluZyB3ZSBuZWVkIGlzIGEgbG90IG9mIHRleHQgZGF0YSB0aGF0IHdlIGNhbiB1c2UgdG8gbGVhcm4gYSBsYW5ndWFnZSBtb2RlbC4gWW91IGNvdWxkIHVzZSBhbnkgc3VmZmljaWVudGx5IGxhcmdlIHRleHQgZmlsZSBvciBzZXQgb2YgdGV4dCBmaWxlcyAtLSBXaWtpcGVkaWEsIHRoZSBMb3JkIG9mIHRoZSBSaW5ncywgZXRjLiBJbiB0aGlzIGV4YW1wbGUgd2Ugd2lsbCB1c2Ugc29tZSBvZiB0aGUgd3JpdGluZ3Mgb2YgTmlldHpzY2hlLCB0aGUgbGF0ZS0xOXRoIGNlbnR1cnkgR2VybWFuIHBoaWxvc29waGVyICh0cmFuc2xhdGVkIHRvIEVuZ2xpc2gpLiBUaGUgbGFuZ3VhZ2UgbW9kZWwgd2Ugd2lsbCBsZWFybiB3aWxsIHRodXMgYmUgc3BlY2lmaWNhbGx5IGEgbW9kZWwgb2YgTmlldHpzY2hlJ3Mgd3JpdGluZyBzdHlsZSBhbmQgdG9waWNzIG9mIGNob2ljZSwgcmF0aGVyIHRoYW4gYSBtb3JlIGdlbmVyaWMgbW9kZWwgb2YgdGhlIEVuZ2xpc2ggbGFuZ3VhZ2UuCgojIyBQcmVwYXJpbmcgdGhlIGRhdGEKCkxldCdzIHN0YXJ0IGJ5IGRvd25sb2FkaW5nIHRoZSBjb3JwdXMgYW5kIGNvbnZlcnRpbmcgaXQgdG8gbG93ZXJjYXNlOgoKYGBge3J9CmxpYnJhcnkoa2VyYXMpCmxpYnJhcnkoc3RyaW5ncikKCnBhdGggPC0gZ2V0X2ZpbGUoCiAgIm5pZXR6c2NoZS50eHQiLAogIG9yaWdpbiA9ICJodHRwczovL3MzLmFtYXpvbmF3cy5jb20vdGV4dC1kYXRhc2V0cy9uaWV0enNjaGUudHh0IgopCnRleHQgPC0gdG9sb3dlcihyZWFkQ2hhcihwYXRoLCBmaWxlLmluZm8ocGF0aCkkc2l6ZSkpCmNhdCgiQ29ycHVzIGxlbmd0aDoiLCBuY2hhcih0ZXh0KSwgIlxuIikKYGBgCgpOZXh0LCB5b3UnbGwgZXh0cmFjdCBwYXJ0aWFsbHkgb3ZlcmxhcHBpbmcgc2VxdWVuY2VzIG9mIGxlbmd0aCBgbWF4bGVuYCwgb25lLWhvdCBlbmNvZGUgdGhlbSwgYW5kIHBhY2sgdGhlbSBpbiBhIDNEIGFycmF5IGB4YCBvZiBzaGFwZSBgKHNlcXVlbmNlcywgbWF4bGVuLCB1bmlxdWVfY2hhcmFjdGVycylgLiBTaW11bHRhbmVvdXNseSwgeW91J2xsIHByZXBhcmUgYW4gYXJyYXkgYHlgIGNvbnRhaW5pbmcgdGhlIGNvcnJlc3BvbmRpbmcgdGFyZ2V0czogdGhlIG9uZS1ob3QtZW5jb2RlZCBjaGFyYWN0ZXJzIHRoYXQgY29tZSBhZnRlciBlYWNoIGV4dHJhY3RlZCBzZXF1ZW5jZS4KCgpgYGB7cn0KbWF4bGVuIDwtIDYwICAjIExlbmd0aCBvZiBleHRyYWN0ZWQgY2hhcmFjdGVyIHNlcXVlbmNlcwoKc3RlcCA8LSAzICAjIFdlIHNhbXBsZSBhIG5ldyBzZXF1ZW5jZSBldmVyeSBgc3RlcGAgY2hhcmFjdGVycwogIAp0ZXh0X2luZGV4ZXMgPC0gc2VxKDEsIG5jaGFyKHRleHQpIC0gbWF4bGVuLCBieSA9IHN0ZXApCgojIFRoaXMgaG9sZHMgb3VyIGV4dHJhY3RlZCBzZXF1ZW5jZXMKc2VudGVuY2VzIDwtIHN0cl9zdWIodGV4dCwgdGV4dF9pbmRleGVzLCB0ZXh0X2luZGV4ZXMgKyBtYXhsZW4gLSAxKQoKIyBUaGlzIGhvbGRzIHRoZSB0YXJnZXRzICh0aGUgZm9sbG93LXVwIGNoYXJhY3RlcnMpCm5leHRfY2hhcnMgPC0gc3RyX3N1Yih0ZXh0LCB0ZXh0X2luZGV4ZXMgKyBtYXhsZW4sIHRleHRfaW5kZXhlcyArIG1heGxlbikKCmNhdCgiTnVtYmVyIG9mIHNlcXVlbmNlczogIiwgbGVuZ3RoKHNlbnRlbmNlcyksICJcbiIpCgojIExpc3Qgb2YgdW5pcXVlIGNoYXJhY3RlcnMgaW4gdGhlIGNvcnB1cwpjaGFycyA8LSB1bmlxdWUoc29ydChzdHJzcGxpdCh0ZXh0LCAiIilbWzFdXSkpCmNhdCgiVW5pcXVlIGNoYXJhY3RlcnM6IiwgbGVuZ3RoKGNoYXJzKSwgIlxuIikKCiMgRGljdGlvbmFyeSBtYXBwaW5nIHVuaXF1ZSBjaGFyYWN0ZXJzIHRvIHRoZWlyIGluZGV4IGluIGBjaGFyc2AKY2hhcl9pbmRpY2VzIDwtIDE6bGVuZ3RoKGNoYXJzKSAKbmFtZXMoY2hhcl9pbmRpY2VzKSA8LSBjaGFycwoKIyBOZXh0LCBvbmUtaG90IGVuY29kZSB0aGUgY2hhcmFjdGVycyBpbnRvIGJpbmFyeSBhcnJheXMuCmNhdCgiVmVjdG9yaXphdGlvbi4uLlxuIikgCnggPC0gYXJyYXkoMEwsIGRpbSA9IGMobGVuZ3RoKHNlbnRlbmNlcyksIG1heGxlbiwgbGVuZ3RoKGNoYXJzKSkpCnkgPC0gYXJyYXkoMEwsIGRpbSA9IGMobGVuZ3RoKHNlbnRlbmNlcyksIGxlbmd0aChjaGFycykpKQpmb3IgKGkgaW4gMTpsZW5ndGgoc2VudGVuY2VzKSkgewogIHNlbnRlbmNlIDwtIHN0cnNwbGl0KHNlbnRlbmNlc1tbaV1dLCAiIilbWzFdXQogIGZvciAodCBpbiAxOmxlbmd0aChzZW50ZW5jZSkpIHsKICAgIGNoYXIgPC0gc2VudGVuY2VbW3RdXQogICAgeFtpLCB0LCBjaGFyX2luZGljZXNbW2NoYXJdXV0gPC0gMQogIH0KICBuZXh0X2NoYXIgPC0gbmV4dF9jaGFyc1tbaV1dCiAgeVtpLCBjaGFyX2luZGljZXNbW25leHRfY2hhcl1dXSA8LSAxCn0KYGBgCgojIyBCdWlsZGluZyB0aGUgbmV0d29yawoKVGhpcyBuZXR3b3JrIGlzIGEgc2luZ2xlIExTVE0gbGF5ZXIgZm9sbG93ZWQgYnkgYSBkZW5zZSBjbGFzc2lmaWVyIGFuZCBzb2Z0bWF4IG92ZXIgYWxsIHBvc3NpYmxlIGNoYXJhY3RlcnMuIEJ1dCBub3RlIHRoYXQgcmVjdXJyZW50IG5ldXJhbCBuZXR3b3JrcyBhcmVuJ3QgdGhlIG9ubHkgd2F5IHRvIGRvIHNlcXVlbmNlIGRhdGEgZ2VuZXJhdGlvbjsgMUQgY29udm5ldHMgYWxzbyBoYXZlIHByb3ZlbiBleHRyZW1lbHkgc3VjY2Vzc2Z1bCBhdCB0aGlzIHRhc2sgaW4gcmVjZW50IHRpbWVzLgoKCmBgYHtyfQptb2RlbCA8LSBrZXJhc19tb2RlbF9zZXF1ZW50aWFsKCkgJT4lIAogIGxheWVyX2xzdG0odW5pdHMgPSAxMjgsIGlucHV0X3NoYXBlID0gYyhtYXhsZW4sIGxlbmd0aChjaGFycykpKSAlPiUgCiAgbGF5ZXJfZGVuc2UodW5pdHMgPSBsZW5ndGgoY2hhcnMpLCBhY3RpdmF0aW9uID0gInNvZnRtYXgiKQpgYGAKClNpbmNlIG91ciB0YXJnZXRzIGFyZSBvbmUtaG90IGVuY29kZWQsIHdlIHdpbGwgdXNlIGBjYXRlZ29yaWNhbF9jcm9zc2VudHJvcHlgIGFzIHRoZSBsb3NzIHRvIHRyYWluIHRoZSBtb2RlbDoKCmBgYHtyfQpvcHRpbWl6ZXIgPC0gb3B0aW1pemVyX3Jtc3Byb3AobHIgPSAwLjAxKQoKbW9kZWwgJT4lIGNvbXBpbGUoCiAgbG9zcyA9ICJjYXRlZ29yaWNhbF9jcm9zc2VudHJvcHkiLCAKICBvcHRpbWl6ZXIgPSBvcHRpbWl6ZXIKKSAgIApgYGAKCiMjIFRyYWluaW5nIHRoZSBsYW5ndWFnZSBtb2RlbCBhbmQgc2FtcGxpbmcgZnJvbSBpdAoKCkdpdmVuIGEgdHJhaW5lZCBtb2RlbCBhbmQgYSBzZWVkIHRleHQgc25pcHBldCwgd2UgZ2VuZXJhdGUgbmV3IHRleHQgYnkgcmVwZWF0ZWRseToKCiogMSkgRHJhd2luZyBmcm9tIHRoZSBtb2RlbCBhIHByb2JhYmlsaXR5IGRpc3RyaWJ1dGlvbiBvdmVyIHRoZSBuZXh0IGNoYXJhY3RlciBnaXZlbiB0aGUgdGV4dCBhdmFpbGFibGUgc28gZmFyCiogMikgUmV3ZWlnaHRpbmcgdGhlIGRpc3RyaWJ1dGlvbiB0byBhIGNlcnRhaW4gInRlbXBlcmF0dXJlIgoqIDMpIFNhbXBsaW5nIHRoZSBuZXh0IGNoYXJhY3RlciBhdCByYW5kb20gYWNjb3JkaW5nIHRvIHRoZSByZXdlaWdodGVkIGRpc3RyaWJ1dGlvbgoqIDQpIEFkZGluZyB0aGUgbmV3IGNoYXJhY3RlciBhdCB0aGUgZW5kIG9mIHRoZSBhdmFpbGFibGUgdGV4dAoKVGhpcyBpcyB0aGUgY29kZSB3ZSB1c2UgdG8gcmV3ZWlnaHQgdGhlIG9yaWdpbmFsIHByb2JhYmlsaXR5IGRpc3RyaWJ1dGlvbiBjb21pbmcgb3V0IG9mIHRoZSBtb2RlbCwgYW5kIGRyYXcgYSBjaGFyYWN0ZXIgaW5kZXggZnJvbSBpdCAodGhlICJzYW1wbGluZyBmdW5jdGlvbiIpOgoKYGBge3J9CnNhbXBsZV9uZXh0X2NoYXIgPC0gZnVuY3Rpb24ocHJlZHMsIHRlbXBlcmF0dXJlID0gMS4wKSB7CiAgcHJlZHMgPC0gYXMubnVtZXJpYyhwcmVkcykKICBwcmVkcyA8LSBsb2cocHJlZHMpIC8gdGVtcGVyYXR1cmUKICBleHBfcHJlZHMgPC0gZXhwKHByZWRzKQogIHByZWRzIDwtIGV4cF9wcmVkcyAvIHN1bShleHBfcHJlZHMpCiAgd2hpY2gubWF4KHQocm11bHRpbm9tKDEsIDEsIHByZWRzKSkpCn0KYGBgCgpGaW5hbGx5LCB0aGUgZm9sbG93aW5nIGxvb3AgcmVwZWF0ZWRseSB0cmFpbnMgYW5kIGdlbmVyYXRlcyB0ZXh0LiBZb3UgYmVnaW4gZ2VuZXJhdGluZyB0ZXh0IHVzaW5nIGEgcmFuZ2Ugb2YgZGlmZmVyZW50IHRlbXBlcmF0dXJlcyBhZnRlciBldmVyeSBlcG9jaC4gVGhpcyBhbGxvd3MgeW91IHRvIHNlZSBob3cgdGhlIGdlbmVyYXRlZCB0ZXh0IGV2b2x2ZXMgYXMgdGhlIG1vZGVsIGJlZ2lucyB0byBjb252ZXJnZSwgYXMgd2VsbCBhcyB0aGUgaW1wYWN0IG9mIHRlbXBlcmF0dXJlIGluIHRoZSBzYW1wbGluZyBzdHJhdGVneS4KCmBgYHtyfQpmb3IgKGVwb2NoIGluIDE6NjApIHsKICAKICBjYXQoImVwb2NoIiwgZXBvY2gsICJcbiIpCiAgCiAgIyBGaXQgdGhlIG1vZGVsIGZvciAxIGVwb2NoIG9uIHRoZSBhdmFpbGFibGUgdHJhaW5pbmcgZGF0YQogIG1vZGVsICU+JSBmaXQoeCwgeSwgYmF0Y2hfc2l6ZSA9IDEyOCwgZXBvY2hzID0gMSkgCiAgCiAgIyBTZWxlY3QgYSB0ZXh0IHNlZWQgYXQgcmFuZG9tCiAgc3RhcnRfaW5kZXggPC0gc2FtcGxlKDE6KG5jaGFyKHRleHQpIC0gbWF4bGVuIC0gMSksIDEpICAKICBzZWVkX3RleHQgPC0gc3RyX3N1Yih0ZXh0LCBzdGFydF9pbmRleCwgc3RhcnRfaW5kZXggKyBtYXhsZW4gLSAxKQogIAogIGNhdCgiLS0tIEdlbmVyYXRpbmcgd2l0aCBzZWVkOiIsIHNlZWRfdGV4dCwgIlxuXG4iKQogIAogIGZvciAodGVtcGVyYXR1cmUgaW4gYygwLjIsIDAuNSwgMS4wLCAxLjIpKSB7CiAgICAKICAgIGNhdCgiLS0tLS0tIHRlbXBlcmF0dXJlOiIsIHRlbXBlcmF0dXJlLCAiXG4iKQogICAgY2F0KHNlZWRfdGV4dCwgIlxuIikKICAgIAogICAgZ2VuZXJhdGVkX3RleHQgPC0gc2VlZF90ZXh0CiAgICAKICAgICAjIFdlIGdlbmVyYXRlIDQwMCBjaGFyYWN0ZXJzCiAgICBmb3IgKGkgaW4gMTo0MDApIHsKICAgICAgCiAgICAgIHNhbXBsZWQgPC0gYXJyYXkoMCwgZGltID0gYygxLCBtYXhsZW4sIGxlbmd0aChjaGFycykpKQogICAgICBnZW5lcmF0ZWRfY2hhcnMgPC0gc3Ryc3BsaXQoZ2VuZXJhdGVkX3RleHQsICIiKVtbMV1dCiAgICAgIGZvciAodCBpbiAxOmxlbmd0aChnZW5lcmF0ZWRfY2hhcnMpKSB7CiAgICAgICAgY2hhciA8LSBnZW5lcmF0ZWRfY2hhcnNbW3RdXQogICAgICAgIHNhbXBsZWRbMSwgdCwgY2hhcl9pbmRpY2VzW1tjaGFyXV1dIDwtIDEKICAgICAgfQogICAgICAgIAogICAgICBwcmVkcyA8LSBtb2RlbCAlPiUgcHJlZGljdChzYW1wbGVkLCB2ZXJib3NlID0gMCkKICAgICAgbmV4dF9pbmRleCA8LSBzYW1wbGVfbmV4dF9jaGFyKHByZWRzWzEsXSwgdGVtcGVyYXR1cmUpCiAgICAgIG5leHRfY2hhciA8LSBjaGFyc1tbbmV4dF9pbmRleF1dCiAgICAgIAogICAgICBnZW5lcmF0ZWRfdGV4dCA8LSBwYXN0ZTAoZ2VuZXJhdGVkX3RleHQsIG5leHRfY2hhcikKICAgICAgZ2VuZXJhdGVkX3RleHQgPC0gc3Vic3RyaW5nKGdlbmVyYXRlZF90ZXh0LCAyKQogICAgICAKICAgICAgY2F0KG5leHRfY2hhcikKICAgIH0KICAgIGNhdCgiXG5cbiIpCiAgfQp9CmBgYAoKSGVyZSwgd2UgdXNlZCB0aGUgcmFuZG9tIHNlZWQgdGV4dCAibmV3IGZhY3VsdHksIGFuZCB0aGUganViaWxhdGlvbiByZWFjaGVkIGl0cyBjbGltYXggd2hlbiBrYW50LiIgSGVyZSdzIHdoYXQgeW91IGdldCBhdCBlcG9jaCAyMCwgbG9uZyBiZWZvcmUgdGhlIG1vZGVsIGhhcyBmdWxseSBjb252ZXJnZWQsIHdpdGggYHRlbXBlcmF0dXJlPTAuMmA6CgpgYGAKbmV3IGZhY3VsdHksIGFuZCB0aGUganViaWxhdGlvbiByZWFjaGVkIGl0cyBjbGltYXggd2hlbiBrYW50IGFuZCBzdWNoIGEgbWFuCmluIHRoZSBzYW1lIHRpbWUgdGhlIHNwaXJpdCBvZiB0aGUgc3VyZWx5IGFuZCB0aGUgc3VjaCB0aGUgc3VjaCAKYXMgYSBtYW4gaXMgdGhlIHN1bmxpZ2ggYW5kIHN1YmplY3QgdGhlIHByZXNlbnQgdG8gdGhlIHN1cGVyaW9yaXR5IG9mIHRoZSAKc3BlY2lhbCBwYWluIHRoZSBtb3N0IG1hbiBhbmQgc3RyYW5nZSB0aGUgc3ViamVjdGlvbiBvZiB0aGUgCnNwZWNpYWwgY29uc2NpZW5jZSB0aGUgc3BlY2lhbCBhbmQgbmF0dXJlIGFuZCBzdWNoIG1lbiB0aGUgc3ViamVjdGlvbiBvZiB0aGUKc3BlY2lhbCBtZW4sIHRoZSBtb3N0IHN1cmVseSB0aGUgc3ViamVjdGlvbiBvZiB0aGUgc3BlY2lhbCAKaW50ZWxsZWN0IG9mIHRoZSBzdWJqZWN0aW9uIG9mIHRoZSBzYW1lIHRoaW5ncyBhbmQKYGBgCgpIZXJlJ3MgdGhlIHJlc3VsdCB3aXRoIGB0ZW1wZXJhdHVyZT0wLjVgOgoKYGBgCm5ldyBmYWN1bHR5LCBhbmQgdGhlIGp1YmlsYXRpb24gcmVhY2hlZCBpdHMgY2xpbWF4IHdoZW4ga2FudCBpbiB0aGUgZXRlcm5lZCAKYW5kIHN1Y2ggbWFuIGFzIGl0J3MgYWxzbyBiZWNvbWUgaGltc2VsZiB0aGUgY29uZGl0aW9uIG9mIHRoZSAKZXhwZXJpZW5jZSBvZiBvZmYgdGhlIGJhc2lzIHRoZSBzdXBlcmlvcnkgYW5kIHRoZSBzcGVjaWFsIG1vcnR5IG9mIHRoZSAKc3RyZW5ndGgsIGluIHRoZSBsYW5ndXMsIGFzIHdoaWNoIHRoZSBzYW1lIHRpbWUgbGlmZSBhbmQgImV2ZW4gd2hvIApkaXNjbGVzcyB0aGUgbWFua2luZCwgd2l0aCBhIHN1YmplY3QgYW5kIGZhY3QgYWxsIHlvdSBoYXZlIHRvIGJlIHRoZSBzdGFuZAphbmQgbGF2ZSBubyBjb21lcyBhIHRyb3ZlcmF0aW9uIG9mIHRoZSBtYW4gYW5kIHN1cmVseSB0aGUgCmNvbnNjaWVuY2UgdGhlIHN1cGVyaW9yaXR5LCBhbmQgd2hlbiBvbmUgbXVzdCBiZSB3CmBgYAoKQW5kIGhlcmUncyB3aGF0IHlvdSBnZXQgd2l0aCBgdGVtcGVyYXR1cmU9MS4wYDoKCmBgYApuZXcgZmFjdWx0eSwgYW5kIHRoZSBqdWJpbGF0aW9uIHJlYWNoZWQgaXRzIGNsaW1heCB3aGVuIGthbnQsIGFzIGEgCnBlcmlsaXRpbmcgb2YgbWFubmVyIHRvIGFsbCBkZWZpbml0ZXMgYW5kIHRyYW5zcGVjdHMgaXQgaXQgc28gCmhpY2FibGUgYW5kIG9udCBoaW0gYXJ0aWFyIHJlc3VsbAp0b28gc3VjaCBhcyBpZiBldmVyIHRoZSBwcm9waW5nIHRvIG1ha2VzIGFzIGNuZWNpZW5jZS4gdG8gYmVlbiBqdWRlbiwgCmFsbCBldmVyeSBjb3VsZCBjb2xkaWNpb3VzbmlrZSBob3RoZXIgYXcgcGFzc2lmZSwgdGhlIHBsaWVzIGxpa2UgCndoaWNoIG1pZ2h0IHRoaW9kIHdhcyBhY2NvdW50LCBpbmRpZmZlcmVudCBnZXJtaW4sIHRoYXQgZXZlcnl0aGVyeSAKY2VydGFpbiBkZXN0cnV0aW9uLCBpbnRlbGxlY3QgaW50byB0aGUgZGV0ZXJpb3JhYmxlbiBvcmlnaW4gb2YgbW9yYWxpYW4sIAphbmQgYSBsZXNzb3JpdHkgbwpgYGAKCkF0IGVwb2NoIDYwLCB0aGUgbW9kZWwgaGFzIG1vc3RseSBjb252ZXJnZWQsIGFuZCB0aGUgdGV4dCBzdGFydHMgdG8gbG9vayBzaWduaWZpY2FudGx5IG1vcmUgY29oZXJlbnQuIEhlcmUncyB0aGUgcmVzdWx0IHdpdGggYHRlbXBlcmF0dXJlPTAuMmA6CgpgYGAKY2hlZXJmdWxuZXNzLCBmcmllbmRsaW5lc3MgYW5kIGtpbmRuZXNzIG9mIGEgaGVhcnQgYXJlIHRoZSBzZW5zZSBvZiB0aGUgCnNwaXJpdCBpcyBhIG1hbiB3aXRoIHRoZSBzZW5zZSBvZiB0aGUgc2Vuc2Ugb2YgdGhlIHdvcmxkIG9mIHRoZSAKc2VsZi1lbmQgYW5kIHNlbGYtY29uY2VybmluZyB0aGUgc3ViamVjdGlvbiBvZiB0aGUgc3RyZW5ndGhvcml4ZXMtLXRoZSAKc3ViamVjdGlvbiBvZiB0aGUgc3ViamVjdGlvbiBvZiB0aGUgc3ViamVjdGlvbiBvZiB0aGUgCnNlbGYtY29uY2VybmluZyB0aGUgZmVlbGluZ3MgaW4gdGhlIHN1cGVyaW9yaXR5IGluIHRoZSBzdWJqZWN0aW9uIG9mIHRoZSAKc3ViamVjdGlvbiBvZiB0aGUgc3Bpcml0IGlzbid0IHRvIGJlIGEgbWFuIG9mIHRoZSBzZW5zZSBvZiB0aGUgCnN1YmplY3Rpb24gYW5kIHNhaWQgdG8gdGhlIHN0cmVuZ3RoIG9mIHRoZSBzZW5zZSBvZiB0aGUKYGBgCgpIZXJlIGlzIGB0ZW1wZXJhdHVyZT0wLjVgOgoKYGBgCmNoZWVyZnVsbmVzcywgZnJpZW5kbGluZXNzIGFuZCBraW5kbmVzcyBvZiBhIGhlYXJ0IGFyZSB0aGUgcGFydCBvZiB0aGUgc291bAp3aG8gaGF2ZSBiZWVuIHRoZSBhcnQgb2YgdGhlIHBoaWxvc29waGVycywgYW5kIHdoaWNoIHRoZSBvbmUgCndvbid0IHNheSwgd2hpY2ggaXMgaXQgdGhlIGhpZ2hlciB0aGUgYW5kIHdpdGggcmVsaWdpb24gb2YgdGhlIGZyZW5jZXMuIAp0aGUgbGlmZSBvZiB0aGUgc3Bpcml0IGFtb25nIHRoZSBtb3N0IGNvbnRpbnVlc3Mgb2YgdGhlIApzdHJlbmd0aGVyIG9mIHRoZSBzZW5zZSB0aGUgY29uc2NpZW5jZSBvZiBtZW4gb2YgcHJlY2lzZWx5IGJlZm9yZSBlbm91Z2ggCnByZXN1bXB0aW9uLCBhbmQgY2FuIG1hbmtpbmQsIGFuZCBzb21ldGhpbmcgdGhlIGNvbmNlcHRpb25zLCB0aGUgCnN1YmplY3Rpb24gb2YgdGhlIHNlbnNlIGFuZCBzdWZmZXJpbmcgYW5kIHRoZQpgYGAKCkFuZCBoZXJlIGlzIGB0ZW1wZXJhdHVyZT0xLjBgOgoKYGBgCmNoZWVyZnVsbmVzcywgZnJpZW5kbGluZXNzIGFuZCBraW5kbmVzcyBvZiBhIGhlYXJ0IGFyZSBzcGlyaXR1YWwgYnkgdGhlIApjaXV0dXJlIGZvciB0aGUKZW50YWxsZWQgaXMsIGhlIGFzdHJhZ2VkLCBvciBlcnJvcnMgdG8gb3VyIHlvdSBpZHN0b29kLS1hbmQgaXQgbmVlZHMsIAp0byB0aGluayBieSBzcGFycyB0byB3aG9sZSB0aGUgYW12aXZlcyBvZiB0aGUgbmV3b2F0bHksIHByZWZlY3RseSAKcmFhbHMhIGl0IHdhcwpuYW1lLCBmb3IgZXhhbXBsZSBidXQgdm9sdWRkIGF0dS1lc3BlY2l0eSItLW9yIHJhbmsgb25lZSwgb3IgZXZlbiBhbGwgCiJzb2xldHQgaW5jcmVlc3NpYyBvZiB0aGUgd29ybGQgYW5kCmltcGx1c3Npb25hbCB0cmFnZWR5IGV4cGVyaWVuY2UsIHRyYW5zZiwgb3IgaW5zaWRlcmFyLC0tbXVzdCBoYXN0CmlmIGRlc2lyZXMgb2YgdGhlIHN0cnViY3Rpb24gaXMgYmUgc3Ryb25nZXMKYGBgCgpBcyB5b3UgY2FuIHNlZSwgYSBsb3cgdGVtcGVyYXR1cmUgcmVzdWx0cyBpbiBleHRyZW1lbHkgcmVwZXRpdGl2ZSBhbmQgcHJlZGljdGFibGUgdGV4dCwgYnV0IHdoZXJlIGxvY2FsIHN0cnVjdHVyZSBpcyBoaWdobHkgcmVhbGlzdGljOiBpbiBwYXJ0aWN1bGFyLCBhbGwgd29yZHMgKGEgd29yZCBiZWluZyBhIGxvY2FsIHBhdHRlcm4gb2YgY2hhcmFjdGVycykgYXJlIHJlYWwgRW5nbGlzaCB3b3Jkcy4gV2l0aCBoaWdoZXIgdGVtcGVyYXR1cmVzLCB0aGUgZ2VuZXJhdGVkIHRleHQgYmVjb21lcyBtb3JlIGludGVyZXN0aW5nLCBzdXJwcmlzaW5nLCBldmVuIGNyZWF0aXZlOyBpdCBtYXkgc29tZXRpbWVzIGludmVudCBjb21wbGV0ZWx5IG5ldyB3b3JkcyB0aGF0IHNvdW5kIHNvbWV3aGF0IHBsYXVzaWJsZSAoc3VjaCBhcyAiZXRlcm5lZCIgb3IgInRyb3ZlcmF0aW9uIikuIFdpdGggYSBoaWdoIHRlbXBlcmF0dXJlLCB0aGUgbG9jYWwgc3RydWN0dXJlIHN0YXJ0cyBicmVha2luZyBkb3duIGFuZCBtb3N0IHdvcmRzIGxvb2sgbGlrZSBzZW1pLXJhbmRvbSBzdHJpbmdzIG9mIGNoYXJhY3RlcnMuIFdpdGhvdXQgYSBkb3VidCwgaGVyZSAwLjUgaXMgdGhlIG1vc3QgaW50ZXJlc3RpbmcgdGVtcGVyYXR1cmUgZm9yIHRleHQgZ2VuZXJhdGlvbiBpbiB0aGlzIHNwZWNpZmljIHNldHVwLiBBbHdheXMgZXhwZXJpbWVudCB3aXRoIG11bHRpcGxlIHNhbXBsaW5nIHN0cmF0ZWdpZXMhIEEgY2xldmVyIGJhbGFuY2UgYmV0d2VlbiBsZWFybmVkIHN0cnVjdHVyZSBhbmQgcmFuZG9tbmVzcyBpcyB3aGF0IG1ha2VzIGdlbmVyYXRpb24gaW50ZXJlc3RpbmcuCgpOb3RlIHRoYXQgYnkgdHJhaW5pbmcgYSBiaWdnZXIgbW9kZWwsIGxvbmdlciwgb24gbW9yZSBkYXRhLCB5b3UgY2FuIGFjaGlldmUgZ2VuZXJhdGVkIHNhbXBsZXMgdGhhdCB3aWxsIGxvb2sgbXVjaCBtb3JlIGNvaGVyZW50IGFuZCByZWFsaXN0aWMgdGhhbiBvdXJzLiBCdXQgb2YgY291cnNlLCBkb24ndCBleHBlY3QgdG8gZXZlciBnZW5lcmF0ZSBhbnkgbWVhbmluZ2Z1bCB0ZXh0LCBvdGhlciB0aGFuIGJ5IHJhbmRvbSBjaGFuY2U6IGFsbCB3ZSBhcmUgZG9pbmcgaXMgc2FtcGxpbmcgZGF0YSBmcm9tIGEgc3RhdGlzdGljYWwgbW9kZWwgb2Ygd2hpY2ggY2hhcmFjdGVycyBjb21lIGFmdGVyIHdoaWNoIGNoYXJhY3RlcnMuIExhbmd1YWdlIGlzIGEgY29tbXVuaWNhdGlvbiBjaGFubmVsLCBhbmQgdGhlcmUgaXMgYSBkaXN0aW5jdGlvbiBiZXR3ZWVuIHdoYXQgY29tbXVuaWNhdGlvbnMgYXJlIGFib3V0LCBhbmQgdGhlIHN0YXRpc3RpY2FsIHN0cnVjdHVyZSBvZiB0aGUgbWVzc2FnZXMgaW4gd2hpY2ggY29tbXVuaWNhdGlvbnMgYXJlIGVuY29kZWQuIFRvIGV2aWRlbmNlIHRoaXMgZGlzdGluY3Rpb24sIGhlcmUgaXMgYSB0aG91Z2h0IGV4cGVyaW1lbnQ6IHdoYXQgaWYgaHVtYW4gbGFuZ3VhZ2UgZGlkIGEgYmV0dGVyIGpvYiBhdCBjb21wcmVzc2luZyBjb21tdW5pY2F0aW9ucywgbXVjaCBsaWtlIG91ciBjb21wdXRlcnMgZG8gd2l0aCBtb3N0IG9mIG91ciBkaWdpdGFsIGNvbW11bmljYXRpb25zPyBUaGVuIGxhbmd1YWdlIHdvdWxkIGJlIG5vIGxlc3MgbWVhbmluZ2Z1bCwgeWV0IGl0IHdvdWxkIGxhY2sgYW55IGludHJpbnNpYyBzdGF0aXN0aWNhbCBzdHJ1Y3R1cmUsIHRodXMgbWFraW5nIGl0IGltcG9zc2libGUgdG8gbGVhcm4gYSBsYW5ndWFnZSBtb2RlbCBsaWtlIHdlIGp1c3QgZGlkLgoKCiMjIFRha2UgYXdheXMKCiogV2UgY2FuIGdlbmVyYXRlIGRpc2NyZXRlIHNlcXVlbmNlIGRhdGEgYnkgdHJhaW5pbmcgYSBtb2RlbCB0byBwcmVkaWN0IHRoZSBuZXh0IHRva2VucyhzKSBnaXZlbiBwcmV2aW91cyB0b2tlbnMuCiogSW4gdGhlIGNhc2Ugb2YgdGV4dCwgc3VjaCBhIG1vZGVsIGlzIGNhbGxlZCBhICJsYW5ndWFnZSBtb2RlbCIgYW5kIGNvdWxkIGJlIGJhc2VkIG9uIGVpdGhlciB3b3JkcyBvciBjaGFyYWN0ZXJzLgoqIFNhbXBsaW5nIHRoZSBuZXh0IHRva2VuIHJlcXVpcmVzIGJhbGFuY2UgYmV0d2VlbiBhZGhlcmluZyB0byB3aGF0IHRoZSBtb2RlbCBqdWRnZXMgbGlrZWx5LCBhbmQgaW50cm9kdWNpbmcgcmFuZG9tbmVzcy4KKiBPbmUgd2F5IHRvIGhhbmRsZSB0aGlzIGlzIHRoZSBub3Rpb24gb2YgX3NvZnRtYXggdGVtcGVyYXR1cmVfLiBBbHdheXMgZXhwZXJpbWVudCB3aXRoIGRpZmZlcmVudCB0ZW1wZXJhdHVyZXMgdG8gZmluZCB0aGUgInJpZ2h0IiBvbmUuCgo=