1 scRNA-Seq data

1.1 UMI

Typical droplet scRNA-seq experiments utilize UMI counts to quantify gene expression in single cell. UMI or Unique Molecular Identifiers are small barcode that are linked to the 3’ end of mRNA molecules before any amplification step (Islam et al. 2013). This technique allows us to easily remove PCR amplification bias from the data.

From the two following figures the figure e or the figure f, which one is representing UMI count data ? Figure 2 Islam et al. 2013

1.2 3’ sequencing

Moreover current typical droplet scRNA-seq experiments rely on 3’ sequencing which means that we don’t have a uniform read distribution along the mRNA molecule sequence. The Feiyang Ma et al. 2010 paper compares a 3’ sequencing method to a classical sequencing method.

Without reading the paper, and from the following figure: which method between KABA or LEXO is the 3’ sequencing one ? Figure 2 Feiyang Ma et al. 2010 paper

1.3 mRNA synthesis

To understand the nature of the data that we are going to analyze, it’s important to understand the mechanisms that generate the observed data. The Breda et al. 2021 paper summarizes these processes in the Figure 1 of their paper.

Figure 1a from the Sanity Breda et al. 2021 paper

Cartoons of the flow of causality from the physical state of the cell to gene expression patterns. The concentrations of transcription factors (TFs), chromatin modifiers and other regulatory factors determine changes in chromatin state, three-dimensional (3D) organization of the chromosomes, binding and unbinding of TFs to promoters and enhancers, and so on. These determine the time-dependent rate \(\lambda_g(t)\) at which gene \(g\) was described a time \(t\) in the past. Similarly, the concentrations of microRNAs, RNases and other RNA-binding proteins determine the time-dependent rate \(\mu_g(t)\) at which mRNAs of gene \(g\) decayed at time \(t\) in the past.

Figure 1b from the Sanity Breda et al. 2021 paper

The transcription activity \(a_g\) of gene \(g\) is defined as the expected number of mRNAs and is a weighted average of its transcription and decay rates in the past. We define the expression state of the cell as the vector \(\vec{\alpha}\) of relative transcription activities of all genes.

Figure 1c from the Sanity Breda et al. 2021 paper

Logical flow from expression state \(\vec{\alpha}_c\) to observed UMI counts \(\vec{n}_c\). The expression state \(\vec{\alpha}_c\) and total transcription activity \(A_c\) determine the transcription activities \(a_{gc}\). For each gene \(g\), the probability \(P(m_{gc}∣a_{gc})\) of having \(m_{gc}\) mRNAs is a Poisson distribution with mean \(a_{gc}\). Assuming each mRNA in cell \(c\) has a probability \(p_c\) of being captured and sequenced, the probability \(P(n_{gc}∣p_c, a_{gc})\) of obtaining \(n_{gc}\) UMIs is a Poisson distribution with mean \(p_{c}a_{gc}\).

Figure 1d from the Sanity Breda et al. 2021 paper

The probability of obtaining the UMI counts \(\vec{n}_c\) given the cell state \(\vec{\alpha}_c\) is a product over genes of Poisson distributions with means \(N_c\alpha_{gc}\), where \(N_c\) is the total UMI count in cell \(c\).

1.4 Zeros

In their 2020 paper, Choi et al. investigate the high proportion of zeros in scRNA-Seq data.

The following figure is typical of droplet based scRNA-Seq. Can you think of some explanation for the presence of so many UMI counts equal to zero ? Figure 1 from the Choi et al. 2020 paper

2 exploring scRNA-seq data

2.1 Single-cell experiment

Before, starting to work with scRNA data, we need a data structure to store these data.

To store and manipulate our data in R, we are going to use the SingleCellExperiment class (from the SingleCellExperiment package). This class implements a data structure that stores all aspects of our single-cell data: gene-by-cell expression data, per-cell metadata and per-gene annotation and manipulate them in a synchronized manner.

This object is used by most of the single-cell package on Bioconductor. The other principal R format used by the Seurate tools suite follows the same kind of format with a count matrix and gene and cell annotation table. In Python the AnnData object has also the same structure, and conversion tools exist to pass from one format to another.

if (!require("BiocManager", quietly = TRUE))
  install.packages("BiocManager")
if (!require("SingleCellExperiment", quietly = TRUE))
  BiocManager::install("SingleCellExperiment")
library(SingleCellExperiment)

2.2 Fake everywhere

As you are future bioinformaticians, we are going to start by working with the best data there is for you: simulated data. For that we will use the Splatter R package that simulates scRNA-Seq data set.

But first we are going to need some libraries:

if (!require("splatter", quietly = TRUE))
  BiocManager::install("splatter")
if (!require("scater", quietly = TRUE))
  BiocManager::install("scater")
if (!require("Seurat", quietly = TRUE))
  install.packages('Seurat')
library(splatter)
library(scater)
library(Seurat)
library(tidyverse)

2.3 simulation parameters

First we need to set the simulation parameters

params <- newSplatParams()

Visualize these parameters (you can use the function str())

The Figure 1 from the Splatter paper explains the simulation parameters and their functions in the data generation process with a DAG from the top to the bottom of the figure.

Figure 1 from the Zappia et al. 2017 paper

We are going to investigate these simulation parameters during the practical.

The Splat simulation uses a hierarchical probabilistic where different aspects of a dataset are generated from appropriate statistical distributions. The first stage generates a means expression level for each gene. These are originally chosen from a Gamma distribution.

First let see the effect of alpha or shape (mean.shape parameter) and beta or rate (mean.rate parameter) on the Gamma distribution density

tibble(
  alpha = seq(from = 1, to = 10, length.out = 5)
) %>% 
  mutate(
    beta = list(seq(from = 0.1, to = 0.9, length.out = 5))
  ) %>% 
  unnest(beta) %>% 
  mutate(
    lambda = map2(alpha, beta, function(x, y){
      rgamma(n = 1000, shape = x, rate = y)
    })
  ) %>% 
  unnest(lambda) %>% 
  ggplot(aes(x = lambda)) +
  geom_histogram(binwidth = 1) +
  facet_wrap(~alpha + beta, scales = "free", labeller = label_both) +
  theme_classic()

Then let see the effect of the shape and rate parameter on the Gamma-Poisson distribution density.

tibble(
  alpha = seq(from = 1, to = 10, length.out = 5)
) %>% 
  mutate(
    beta = list(seq(from = 0.1, to = 0.9, length.out = 5))
  ) %>% 
  unnest(beta) %>% 
  mutate(
    count = map2(alpha, beta, function(x, y){
     rgamma(n = 1000, shape = x, rate = y) %>%  
      map_dbl(function(x){rpois(n = 1, lambda = x)})
    })
  ) %>% 
  unnest(count) %>% 
  ggplot(aes(x = count)) +
  geom_histogram(binwidth = 1) +
  facet_wrap(~alpha + beta, scales = "free", labeller = label_both) +
  theme_classic()

Why do you think that a Gamma-Poisson is more realistic than a Poisson distribution for a given gene and a homogeneous population of cells ?

Do you know another distribution name that can correspond to this kind of data ?

To better understand what we are doing we are going to first work with 2000 gene and 1000 cells:

params <- setParam(params, "nGenes", 2000)
params <- setParam(params, "batchCells", 1000)

For some genes that are selected to be outliers with high expression, a factor is generated from a log-normal distribution. These factors are then multiplied by the median gene mean to create new means for those genes.

# Few outliers
sim1 <- splatSimulate(out.prob = 0.001, verbose = FALSE)
ggplot(as.data.frame(rowData(sim1)),
     aes(x = log10(GeneMean), fill = OutlierFactor != 1)) +
  geom_histogram(bins = 100) +
  ggtitle("Few outliers") +
  theme_classic()

# Lots of outliers
sim2 <- splatSimulate(out.prob = 0.2, verbose = FALSE)
ggplot(as.data.frame(rowData(sim2)),
     aes(x = log10(GeneMean), fill = OutlierFactor != 1)) +
  geom_histogram(bins = 100) +
  ggtitle("Lots of outliers") +
  theme_classic()

The library sizes are then used to scale the gene means for each cell, resulting in a range a counts per cell in the simulated dataset. The gene means are then further adjusted to enforce a relationship between the mean expression level and the variability.

What is a library in scRNA-Seq compared to bulk RNA-Seq ?

The lib.loc, lib.scale define the mean and standard deviation of the logNormal distribution from which is drawn the library size factor.

The final cell by gene matrix of genes means is then used to generate a count matrix using a Poisson distribution. The result is a synthetic dataset consisting of counts from a Gamma-Poisson (or negative-binomial) distribution. An additional optional step can be used to replicate a “dropout” effect. A probability of dropout is generated using a logistic function based on the underlying mean expression level. A Bernoulli distribution is then used to create a dropout matrix which sets some of the generated counts to zero.

params <- setParam(params, "dropout.type", "none")

The model described here will generate a single population of cells but the Splat simulation has been designed to be as flexible as possible and can create scenarios including multiple groups of cells (cell types), continuous paths between cell types and multiple experimental batches. The parameters used to create these types of simulations and how they interact with the model are described below. We then remove the batch effect

sim <- splatSimulate(params)

Use the rowData() and colData() function to explore the additional data stored in the sce experiment by splatter

rowData(sim)
DataFrame with 2000 rows and 4 columns
                Gene BaseGeneMean OutlierFactor   GeneMean
         <character>    <numeric>     <numeric>  <numeric>
Gene1          Gene1      3.15483             1    3.15483
Gene2          Gene2      0.66007             1    0.66007
Gene3          Gene3     12.62170             1   12.62170
Gene4          Gene4      3.52125             1    3.52125
Gene5          Gene5      2.20508             1    2.20508
...              ...          ...           ...        ...
Gene1996    Gene1996    1.0380931       88.9158 92.1664727
Gene1997    Gene1997    0.4809314        1.0000  0.4809314
Gene1998    Gene1998    0.0965045        1.0000  0.0965045
Gene1999    Gene1999    4.9303710        1.0000  4.9303710
Gene2000    Gene2000    2.5029670        1.0000  2.5029670
colData(sim)
DataFrame with 1000 rows and 3 columns
                Cell       Batch ExpLibSize
         <character> <character>  <numeric>
Cell1          Cell1      Batch1    59933.2
Cell2          Cell2      Batch1    62984.3
Cell3          Cell3      Batch1    62835.8
Cell4          Cell4      Batch1    50426.9
Cell5          Cell5      Batch1    55122.0
...              ...         ...        ...
Cell996      Cell996      Batch1    51399.2
Cell997      Cell997      Batch1    50360.5
Cell998      Cell998      Batch1    61134.5
Cell999      Cell999      Batch1    58652.6
Cell1000    Cell1000      Batch1    62018.3

2.4 Data visualization

We can use scater to visualize the sim data

# PCA plot using scater
sim <- logNormCounts(sim) # add log1p assay
sim <- runPCA(sim) # add PCA results in the dimension reduction tables
plotPCA(sim, colour_by = "Batch")

2.4.1 Zeros plots

Try to reproduce the 1.4 Zeros plot using the counts() function

We add the zero_n annotation to the sce object:

rowData(sim)["zero_n"] <- rowSums(counts(sim) == 0)
rowData(sim)["sum_gene"] <- rowSums(counts(sim))
colData(sim)["zero_n"] <- colSums(counts(sim) == 0)
colData(sim)["sum_cell"] <- colSums(counts(sim))
colData(sim) %>% 
  as_tibble() %>% 
  ggplot(aes(x = sum_cell, y = zero_n)) +
  geom_point() +
  scale_x_log10() +
  theme_classic()

rowData(sim) %>% 
  as_tibble() %>% 
  ggplot(aes(x = sum_gene/10e3, y = zero_n)) +
  geom_point() +
  scale_x_log10() +
  theme_classic()

2.4.2 Realistic simulation

To simulate data that look more like real one, we can use the parameters of a real dataset. We start by downloading the following 10X genomics dataset:

In the terminal get the data set:

wget https://s3-us-west-2.amazonaws.com/10x.files/samples/cell/pbmc3k/pbmc3k_filtered_gene_bc_matrices.tar.gz
tar -xvf pbmc3k_filtered_gene_bc_matrices.tar.gz

We then use this data set to create an sce object. We are going to use this sce object to estimate geologically relevant parameters for our simulated data.

sce <- SingleCellExperiment(
  Seurat::Read10X(data.dir = "filtered_gene_bc_matrices/hg19/")
)
params_real <- assay(sce) %>% 
  as.matrix() %>% 
  t() %>% 
  as.data.frame() %>% 
  sample_n(100) %>% # subsample cell to be faster
  t() %>% 
  splatter::splatEstimate()

We can then simulate our data

sim <- splatSimulate(params_real, nGenes = 2000, batchCells = 1000, verbose = F)

Is the cells plot more realistic ?

rowData(sim)["zero_n"] <- rowSums(counts(sim) == 0)
rowData(sim)["sum_gene"] <- rowSums(counts(sim))
colData(sim)["zero_n"] <- colSums(counts(sim) == 0)
colData(sim)["sum_cell"] <- colSums(counts(sim))

colData(sim) %>% 
  as_tibble() %>% 
  ggplot(aes(x = sum_cell, y = zero_n)) +
  geom_point() +
  scale_x_log10() +
  theme_classic()

2.4.3 Coefficient of Variation plot

Finally let’s check the mean versus CV variation

rowData(sim)["mean"] <- rowMeans(counts(sim))
rowData(sim)["var"] <- rowVars(counts(sim))
rowData(sim)["CV"] <- rowData(sim)["var"][, 1] / rowData(sim)["mean"][, 1]

rowData(sim) %>% 
  as_tibble() %>% 
  ggplot(aes(x = mean, y = CV)) +
  geom_point() +
  scale_x_log10() +
  geom_hline(yintercept = 1, color = "red") +
  theme_classic()

rowData(sim) %>% 
  as_tibble() %>% 
  ggplot(aes(x = mean, y = var)) +
  geom_point() +
  scale_y_log10() +
  scale_x_log10() +
  geom_abline(yintercept = 0, slop = 1, color = "red") +
  theme_classic()

What can you tell about this relation ? What is the link with the Gamma-Poisson model ?

2.5 Groups of cells

In real data set, we often have different cell types in a data set. In a classical analysis, you are going to have to identify these groups (clustering) and do various analyses between these groups (differential expression analysis, etc.).

We can use splatter to simulate groups.

The splatSimulateGroups() function can take the following parameters:

  • group.prob is a vector of group proportion that sum to 1
  • de.prob is the proportion of differentially expressed genes in each group
  • de.downProb is the proportion of down-regulated genes in each group
  • de.facLoc is the location value for each group
  • de.facSacle is the scale value for each group

Try to change the splatSimulateGroups() parameters to see their effect on the PCA representation

sim <- splatSimulateGroups(params,
                            batchCells = 500,
                            nGenes = 1000,
                            group.prob = c(0.05, 0.2, 0.2, 0.2, 0.35),
                            de.prob = c(0.3, 0.1, 0.2, 0.01, 0.1),
                            de.downProb = c(0.1, 0.4, 0.9, 0.6, 0.5),
                            verbose = FALSE)
sim <- logNormCounts(sim)
sim <- runPCA(sim)
plotPCA(sim, colour_by = "Group") +
    labs(title = "Different DE factors",
         caption = paste(
             "Group 1 is small with many very up-regulated DE genes,",
             "Group 2 has the default DE parameters,\n",
             "Group 3 has many down-regulated DE genes,",
             "Group 4 has very few DE genes,",
             "Group 5 is large with moderate DE factors")
         )

2.6 Paths of cells

Sometime, in scRNA-Seq instead of having discreet cell-type we observe a continuous path of cell state. This is the case for cell differentiation, for example.

We can use splatter to simulate paths.

The splatSimulateGroups() function can take the following parameters:

  • path.from is a vector of the group order (stating from zero)
sim <- splatSimulatePaths(params,
                            batchCells = 500,
                            nGenes = 1000,
                           group.prob = c(0.25, 0.25, 0.25, 0.25),
                           de.prob = 0.8, de.facLoc = 0.2,
                           path.from = c(0, 1, 2, 3),
                           verbose = FALSE)
sim <- logNormCounts(sim)
sim <- runPCA(sim)
plotPCA(sim, colour_by = "Group") + ggtitle("Linear paths")

2.7 Batches

Finally, in some experiment, the number of cells is too high to be sequenced in one go. For these datasets you will have batch effects.

In splatter, If you give a vector of integers to the batchCells parameters, you will simulate batches.

sim <- splatSimulateGroups(params,
                            batchCells = c(500, 500),
                            nGenes = 1000,
                            group.prob = c(0.05, 0.2, 0.2, 0.2, 0.35),
                            de.prob = c(0.3, 0.1, 0.2, 0.01, 0.1),
                            de.downProb = c(0.1, 0.4, 0.9, 0.6, 0.5),
                            verbose = FALSE)
sim <- logNormCounts(sim)
sim <- runPCA(sim)
plotPCA(sim, colour_by = "Group", shape_by = "Batch") +
    labs(title = "Different DE factors",
         caption = paste(
             "Group 1 is small with many very up-regulated DE genes,",
             "Group 2 has the default DE parameters,\n",
             "Group 3 has many down-regulated DE genes,",
             "Group 4 has very few DE genes,",
             "Group 5 is large with moderate DE factors")
         )

Click on the Next link

LS0tCnRpdGxlOiAic2NSTkEtc2VxOiBOYXR1cmUgb2YgdGhlIGRhdGEiCmF1dGhvcjogTGF1cmVudCBNb2RvbG8KZGF0ZTogMjAyMS0yMDIyCm91dHB1dDoKICAgIGh0bWxfbm90ZWJvb2s6CiAgICAgIHRvYzogdHJ1ZQogICAgICB0b2NfZmxvYXQ6CiAgICAgICAgY29sbGFwc2VkOiBmYWxzZQogICAgICAgIHNtb290aF9zY3JvbGw6IGZhbHNlCiAgICAgIG51bWJlcl9zZWN0aW9uczogdHJ1ZQogICAgICB0aGVtZTogc2FuZHN0b25lCiAgICAgIGhpZ2hsaWdodDogcHlnbWVudHMKLS0tCgpgYGB7ciBzZXR1cCwgaW5jbHVkZT1GfQprbml0cjo6b3B0c19jaHVuayRzZXQoCiAgZWNobyA9IFQsCiAgd2FybmluZyA9IEYsCiAgbWVzc2FnZSA9IEYsCiAgY2FjaGUgPSBULAogIHJvb3QuZGlyID0gIi4uIiwKICBmaXQud2lkdGggPSAxMCwKICBmaWcuaGVpZ2h0ID0gNSwKICBmaWcucGF0aCA9ICcuL2ltZy8nLAogIGRwaSA9IDEwMCwKICBwcm9ncmVzcyA9IFRSVUUKKQpgYGAKCiMgc2NSTkEtU2VxIGRhdGEKCiMjIFVNSQoKVHlwaWNhbCBkcm9wbGV0IHNjUk5BLXNlcSBleHBlcmltZW50cyB1dGlsaXplIFVNSSBjb3VudHMgdG8gcXVhbnRpZnkgZ2VuZSBleHByZXNzaW9uIGluIHNpbmdsZSBjZWxsLgpVTUkgb3IgVW5pcXVlIE1vbGVjdWxhciBJZGVudGlmaWVycyBhcmUgc21hbGwgYmFyY29kZSB0aGF0IGFyZSBsaW5rZWQgdG8gdGhlIDMnIGVuZCBvZiBtUk5BIG1vbGVjdWxlcyBiZWZvcmUgYW55IGFtcGxpZmljYXRpb24gc3RlcCAoW0lzbGFtIGV0IGFsLiAyMDEzXShodHRwczovL3d3dy5uYXR1cmUuY29tL2FydGljbGVzL25tZXRoLjI3NzIpKS4KVGhpcyB0ZWNobmlxdWUgYWxsb3dzIHVzIHRvIGVhc2lseSByZW1vdmUgUENSIGFtcGxpZmljYXRpb24gYmlhcyBmcm9tIHRoZSBkYXRhLgoKPiBGcm9tIHRoZSB0d28gZm9sbG93aW5nIGZpZ3VyZXMgdGhlIGZpZ3VyZSAqKmUqKiBvciB0aGUgZmlndXJlICoqZioqLCB3aGljaCBvbmUgaXMgcmVwcmVzZW50aW5nIFVNSSBjb3VudCBkYXRhID8KPiAhW0ZpZ3VyZSAyIElzbGFtIGV0IGFsLiAyMDEzXSguL2ltZy9yZWFkX3ZzX3VtaS5wbmcpCgoKIyMgMycgc2VxdWVuY2luZwoKTW9yZW92ZXIgY3VycmVudCB0eXBpY2FsIGRyb3BsZXQgc2NSTkEtc2VxIGV4cGVyaW1lbnRzIHJlbHkgb24gMycgc2VxdWVuY2luZyB3aGljaCBtZWFucyB0aGF0IHdlIGRvbid0IGhhdmUgYSB1bmlmb3JtIHJlYWQgZGlzdHJpYnV0aW9uIGFsb25nIHRoZSBtUk5BIG1vbGVjdWxlIHNlcXVlbmNlLgpUaGUgW0ZlaXlhbmcgTWEgZXQgYWwuIDIwMTAgcGFwZXJdKGh0dHBzOi8vZG9pLm9yZy8xMC4xMTg2L3MxMjg2NC0wMTgtNTM5My0zKSBjb21wYXJlcyBhIDMnIHNlcXVlbmNpbmcgbWV0aG9kIHRvIGEgY2xhc3NpY2FsIHNlcXVlbmNpbmcgbWV0aG9kLgoKPiBXaXRob3V0IHJlYWRpbmcgdGhlIHBhcGVyLCBhbmQgZnJvbSB0aGUgZm9sbG93aW5nIGZpZ3VyZTogd2hpY2ggbWV0aG9kIGJldHdlZW4gKipLQUJBKiogb3IgKipMRVhPKiogaXMgdGhlIDMnIHNlcXVlbmNpbmcgb25lID8KPiAhW0ZpZ3VyZSAyIEZlaXlhbmcgTWEgZXQgYWwuIDIwMTAgcGFwZXJdKC4vaW1nL2thcGFfdnNfbGV4b2dlbi5wbmcpCgojIyBtUk5BIHN5bnRoZXNpcwoKVG8gdW5kZXJzdGFuZCB0aGUgbmF0dXJlIG9mIHRoZSBkYXRhIHRoYXQgd2UgYXJlIGdvaW5nIHRvIGFuYWx5emUsIGl0J3MgaW1wb3J0YW50IHRvIHVuZGVyc3RhbmQgdGhlIG1lY2hhbmlzbXMgdGhhdCBnZW5lcmF0ZSB0aGUgb2JzZXJ2ZWQgZGF0YS4gVGhlIFtCcmVkYSBldCBhbC4gMjAyMSBwYXBlciBzdW1tYXJpemVzXShodHRwczovL2RvaS5vcmcvMTAuMTAzOC9zNDE1ODctMDIxLTAwODc1LXgpIHRoZXNlIHByb2Nlc3NlcyBpbiB0aGUgRmlndXJlIDEgb2YgdGhlaXIgcGFwZXIuCgoKIVtGaWd1cmUgMWEgZnJvbSB0aGUgU2FuaXR5IEJyZWRhIGV0IGFsLiAyMDIxIHBhcGVyXSguL2ltZy9zYW5pdHlfYS5wbmcpCgpDYXJ0b29ucyBvZiB0aGUgZmxvdyBvZiBjYXVzYWxpdHkgZnJvbSB0aGUgcGh5c2ljYWwgc3RhdGUgb2YgdGhlIGNlbGwgdG8gZ2VuZSBleHByZXNzaW9uIHBhdHRlcm5zLgpUaGUgY29uY2VudHJhdGlvbnMgb2YgdHJhbnNjcmlwdGlvbiBmYWN0b3JzIChURnMpLCBjaHJvbWF0aW4gbW9kaWZpZXJzIGFuZCBvdGhlciByZWd1bGF0b3J5IGZhY3RvcnMgZGV0ZXJtaW5lIGNoYW5nZXMgaW4gY2hyb21hdGluIHN0YXRlLCB0aHJlZS1kaW1lbnNpb25hbCAoM0QpIG9yZ2FuaXphdGlvbiBvZiB0aGUgY2hyb21vc29tZXMsIGJpbmRpbmcgYW5kIHVuYmluZGluZyBvZiBURnMgdG8gcHJvbW90ZXJzIGFuZCBlbmhhbmNlcnMsIGFuZCBzbyBvbi4KVGhlc2UgZGV0ZXJtaW5lIHRoZSB0aW1lLWRlcGVuZGVudCByYXRlICRcbGFtYmRhX2codCkkIGF0IHdoaWNoIGdlbmUgJGckIHdhcyBkZXNjcmliZWQgYSB0aW1lICR0JCBpbiB0aGUgcGFzdC4KU2ltaWxhcmx5LCB0aGUgY29uY2VudHJhdGlvbnMgb2YgbWljcm9STkFzLCBSTmFzZXMgYW5kIG90aGVyIFJOQS1iaW5kaW5nIHByb3RlaW5zIGRldGVybWluZSB0aGUgdGltZS1kZXBlbmRlbnQgcmF0ZSAkXG11X2codCkkIGF0IHdoaWNoIG1STkFzIG9mIGdlbmUgJGckIGRlY2F5ZWQgYXQgdGltZSAkdCQgaW4gdGhlIHBhc3QuCgoKIVtGaWd1cmUgMWIgZnJvbSB0aGUgU2FuaXR5IEJyZWRhIGV0IGFsLiAyMDIxIHBhcGVyXSguL2ltZy9zYW5pdHlfYi5wbmcpCgpUaGUgdHJhbnNjcmlwdGlvbiBhY3Rpdml0eSAkYV9nJCBvZiBnZW5lICRnJCBpcyBkZWZpbmVkIGFzIHRoZSBleHBlY3RlZCBudW1iZXIgb2YgbVJOQXMgYW5kIGlzIGEgd2VpZ2h0ZWQgYXZlcmFnZSBvZiBpdHMgdHJhbnNjcmlwdGlvbiBhbmQgZGVjYXkgcmF0ZXMgaW4gdGhlIHBhc3QuCldlIGRlZmluZSB0aGUgZXhwcmVzc2lvbiBzdGF0ZSBvZiB0aGUgY2VsbCBhcyB0aGUgdmVjdG9yICRcdmVje1xhbHBoYX0kIG9mIHJlbGF0aXZlIHRyYW5zY3JpcHRpb24gYWN0aXZpdGllcyBvZiBhbGwgZ2VuZXMuCgohW0ZpZ3VyZSAxYyBmcm9tIHRoZSBTYW5pdHkgQnJlZGEgZXQgYWwuIDIwMjEgcGFwZXJdKC4vaW1nL3Nhbml0eV9jLnBuZykKCkxvZ2ljYWwgZmxvdyBmcm9tIGV4cHJlc3Npb24gc3RhdGUgJFx2ZWN7XGFscGhhfV9jJCB0byBvYnNlcnZlZCBVTUkgY291bnRzICRcdmVje259X2MkLgpUaGUgZXhwcmVzc2lvbiBzdGF0ZSAkXHZlY3tcYWxwaGF9X2MkIGFuZCB0b3RhbCB0cmFuc2NyaXB0aW9uIGFjdGl2aXR5ICRBX2MkIGRldGVybWluZSB0aGUgdHJhbnNjcmlwdGlvbiBhY3Rpdml0aWVzICRhX3tnY30kLgpGb3IgZWFjaCBnZW5lICRnJCwgdGhlIHByb2JhYmlsaXR5ICRQKG1fe2djfeKIo2Ffe2djfSkkIG9mIGhhdmluZyAkbV97Z2N9JCBtUk5BcyBpcyBhIFBvaXNzb24gZGlzdHJpYnV0aW9uIHdpdGggbWVhbiAkYV97Z2N9JC4KQXNzdW1pbmcgZWFjaCBtUk5BIGluIGNlbGwgJGMkIGhhcyBhIHByb2JhYmlsaXR5ICRwX2MkIG9mIGJlaW5nIGNhcHR1cmVkIGFuZCBzZXF1ZW5jZWQsIHRoZSBwcm9iYWJpbGl0eSAkUChuX3tnY33iiKNwX2MsIGFfe2djfSkkIG9mIG9idGFpbmluZyAkbl97Z2N9JCBVTUlzIGlzIGEgUG9pc3NvbiBkaXN0cmlidXRpb24gd2l0aCBtZWFuICRwX3tjfWFfe2djfSQuCgohW0ZpZ3VyZSAxZCBmcm9tIHRoZSBTYW5pdHkgQnJlZGEgZXQgYWwuIDIwMjEgcGFwZXJdKC4vaW1nL3Nhbml0eV9kLnBuZykKClRoZSBwcm9iYWJpbGl0eSBvZiBvYnRhaW5pbmcgdGhlIFVNSSBjb3VudHMgJFx2ZWN7bn1fYyQgZ2l2ZW4gdGhlIGNlbGwgc3RhdGUgJFx2ZWN7XGFscGhhfV9jJCBpcyBhIHByb2R1Y3Qgb3ZlciBnZW5lcyBvZiBQb2lzc29uIGRpc3RyaWJ1dGlvbnMgd2l0aCBtZWFucyAkTl9jXGFscGhhX3tnY30kLCB3aGVyZSAkTl9jJCBpcyB0aGUgdG90YWwgVU1JIGNvdW50IGluIGNlbGwgJGMkLgoKIyMgWmVyb3MKCkluIHRoZWlyIFsyMDIwIHBhcGVyLCBDaG9pIGV0IGFsLl0oaHR0cHM6Ly9kb2kub3JnLzEwLjExODYvczEzMDU5LTAyMC0wMjEwMy0yKSBpbnZlc3RpZ2F0ZSB0aGUgaGlnaCBwcm9wb3J0aW9uIG9mIHplcm9zIGluIHNjUk5BLVNlcSBkYXRhLgoKPiBUaGUgZm9sbG93aW5nIGZpZ3VyZSBpcyB0eXBpY2FsIG9mIGRyb3BsZXQgYmFzZWQgc2NSTkEtU2VxLgo+IENhbiB5b3UgdGhpbmsgb2Ygc29tZSBleHBsYW5hdGlvbiBmb3IgdGhlIHByZXNlbmNlIG9mIHNvIG1hbnkgVU1JIGNvdW50cyBlcXVhbCB0byB6ZXJvID8KPiAhW0ZpZ3VyZSAxIGZyb20gdGhlIENob2kgZXQgYWwuIDIwMjAgcGFwZXJdKC4vaW1nL2Nob2lfZXRfYWxfZmlnMS5wbmcpCgojIGV4cGxvcmluZyBzY1JOQS1zZXEgZGF0YQoKIyMgU2luZ2xlLWNlbGwgZXhwZXJpbWVudAoKQmVmb3JlLCBzdGFydGluZyB0byB3b3JrIHdpdGggc2NSTkEgZGF0YSwgd2UgbmVlZCBhIGRhdGEgc3RydWN0dXJlIHRvIHN0b3JlIHRoZXNlIGRhdGEuCgpUbyBzdG9yZSBhbmQgbWFuaXB1bGF0ZSBvdXIgZGF0YSBpbiBSLCB3ZSBhcmUgZ29pbmcgdG8gdXNlIHRoZSBgU2luZ2xlQ2VsbEV4cGVyaW1lbnRgIGNsYXNzIChmcm9tIHRoZSBbU2luZ2xlQ2VsbEV4cGVyaW1lbnRdKGh0dHBzOi8vYmlvY29uZHVjdG9yLm9yZy9wYWNrYWdlcy8zLjExL1NpbmdsZUNlbGxFeHBlcmltZW50KSBwYWNrYWdlKS4KVGhpcyBjbGFzcyBpbXBsZW1lbnRzIGEgZGF0YSBzdHJ1Y3R1cmUgdGhhdCBzdG9yZXMgYWxsIGFzcGVjdHMgb2Ygb3VyIHNpbmdsZS1jZWxsIGRhdGE6IGdlbmUtYnktY2VsbCBleHByZXNzaW9uIGRhdGEsIHBlci1jZWxsIG1ldGFkYXRhIGFuZCBwZXItZ2VuZSBhbm5vdGF0aW9uIGFuZCBtYW5pcHVsYXRlIHRoZW0gaW4gYSBzeW5jaHJvbml6ZWQgbWFubmVyLgoKIVtdKC4vaW1nL1NpbmdsZUNlbGxFeHBlcmltZW50LnBuZykKClRoaXMgb2JqZWN0IGlzIHVzZWQgYnkgbW9zdCBvZiB0aGUgc2luZ2xlLWNlbGwgcGFja2FnZSBvbiBCaW9jb25kdWN0b3IuClRoZSBvdGhlciBwcmluY2lwYWwgUiBmb3JtYXQgdXNlZCBieSB0aGUgW1NldXJhdGUgdG9vbHMgc3VpdGVdKGh0dHBzOi8vc2F0aWphbGFiLm9yZy9zZXVyYXQvKSBmb2xsb3dzIHRoZSBzYW1lIGtpbmQgb2YgZm9ybWF0IHdpdGggYSBjb3VudCBtYXRyaXggYW5kIGdlbmUgYW5kIGNlbGwgYW5ub3RhdGlvbiB0YWJsZS4gCkluIFB5dGhvbiB0aGUgW0FubkRhdGEgb2JqZWN0XShodHRwczovL3NjYW5weS5yZWFkdGhlZG9jcy5pby9lbi9zdGFibGUvdXNhZ2UtcHJpbmNpcGxlcy5odG1sI2FubmRhdGEpIGhhcyBhbHNvIHRoZSBzYW1lIHN0cnVjdHVyZSwgYW5kIGNvbnZlcnNpb24gdG9vbHMgZXhpc3QgdG8gcGFzcyBmcm9tIG9uZSBmb3JtYXQgdG8gYW5vdGhlci4KCmBgYHtyIHNjZV9vYmplY3QsIGNhY2hlPVQsIGVjaG89VCwgbWVzc2FnZT1GLCB3YXJuaW5nPUZ9CmlmICghcmVxdWlyZSgiQmlvY01hbmFnZXIiLCBxdWlldGx5ID0gVFJVRSkpCiAgaW5zdGFsbC5wYWNrYWdlcygiQmlvY01hbmFnZXIiKQppZiAoIXJlcXVpcmUoIlNpbmdsZUNlbGxFeHBlcmltZW50IiwgcXVpZXRseSA9IFRSVUUpKQogIEJpb2NNYW5hZ2VyOjppbnN0YWxsKCJTaW5nbGVDZWxsRXhwZXJpbWVudCIpCmxpYnJhcnkoU2luZ2xlQ2VsbEV4cGVyaW1lbnQpCmBgYAoKIyMgRmFrZSBldmVyeXdoZXJlCgpBcyB5b3UgYXJlIGZ1dHVyZSBiaW9pbmZvcm1hdGljaWFucywgd2UgYXJlIGdvaW5nIHRvIHN0YXJ0IGJ5IHdvcmtpbmcgd2l0aCB0aGUgYmVzdCBkYXRhIHRoZXJlIGlzIGZvciB5b3U6IHNpbXVsYXRlZCBkYXRhLgpGb3IgdGhhdCB3ZSB3aWxsIHVzZSB0aGUgW1NwbGF0dGVyXShodHRwczovL2RvaS5vcmcvMTAuMTE4Ni9zMTMwNTktMDE3LTEzMDUtMCkgUiBwYWNrYWdlIHRoYXQgc2ltdWxhdGVzIHNjUk5BLVNlcSBkYXRhIHNldC4KCkJ1dCBmaXJzdCB3ZSBhcmUgZ29pbmcgdG8gbmVlZCBzb21lIGxpYnJhcmllczoKCmBgYHtyIGxvYWRfc3BsYXR0ZXIsIGNhY2hlPVQsIGVjaG89VH0KaWYgKCFyZXF1aXJlKCJzcGxhdHRlciIsIHF1aWV0bHkgPSBUUlVFKSkKICBCaW9jTWFuYWdlcjo6aW5zdGFsbCgic3BsYXR0ZXIiKQppZiAoIXJlcXVpcmUoInNjYXRlciIsIHF1aWV0bHkgPSBUUlVFKSkKICBCaW9jTWFuYWdlcjo6aW5zdGFsbCgic2NhdGVyIikKaWYgKCFyZXF1aXJlKCJTZXVyYXQiLCBxdWlldGx5ID0gVFJVRSkpCiAgaW5zdGFsbC5wYWNrYWdlcygnU2V1cmF0JykKbGlicmFyeShzcGxhdHRlcikKbGlicmFyeShzY2F0ZXIpCmxpYnJhcnkoU2V1cmF0KQpsaWJyYXJ5KHRpZHl2ZXJzZSkKYGBgCgojIyBzaW11bGF0aW9uIHBhcmFtZXRlcnMKCkZpcnN0IHdlIG5lZWQgdG8gc2V0IHRoZSBzaW11bGF0aW9uIHBhcmFtZXRlcnMKCmBgYHtyIGZpcnN0X3NpbV9wYXJhbXN9CnBhcmFtcyA8LSBuZXdTcGxhdFBhcmFtcygpCmBgYAoKPiBWaXN1YWxpemUgdGhlc2UgcGFyYW1ldGVycyAoeW91IGNhbiB1c2UgdGhlIGZ1bmN0aW9uIGBzdHIoKWApCgpUaGUgRmlndXJlIDEgZnJvbSB0aGUgW1NwbGF0dGVyXShodHRwczovL2RvaS5vcmcvMTAuMTE4Ni9zMTMwNTktMDE3LTEzMDUtMCkgcGFwZXIgZXhwbGFpbnMgdGhlIHNpbXVsYXRpb24gcGFyYW1ldGVycyBhbmQgdGhlaXIgZnVuY3Rpb25zIGluIHRoZSBkYXRhIGdlbmVyYXRpb24gcHJvY2VzcyB3aXRoIGEgREFHIGZyb20gdGhlIHRvcCB0byB0aGUgYm90dG9tIG9mIHRoZSBmaWd1cmUuCgohW0ZpZ3VyZSAxIGZyb20gdGhlIFphcHBpYSBldCBhbC4gMjAxNyBwYXBlcl0oLi9pbWcvc3BsYXR0ZXIucG5nKQoKPiBXZSBhcmUgZ29pbmcgdG8gaW52ZXN0aWdhdGUgdGhlc2Ugc2ltdWxhdGlvbiBwYXJhbWV0ZXJzIGR1cmluZyB0aGUgcHJhY3RpY2FsLgoKVGhlIFNwbGF0IHNpbXVsYXRpb24gdXNlcyBhIGhpZXJhcmNoaWNhbCBwcm9iYWJpbGlzdGljIHdoZXJlIGRpZmZlcmVudCBhc3BlY3RzIG9mIGEgZGF0YXNldCBhcmUgZ2VuZXJhdGVkIGZyb20gYXBwcm9wcmlhdGUgc3RhdGlzdGljYWwgZGlzdHJpYnV0aW9ucy4gVGhlIGZpcnN0IHN0YWdlIGdlbmVyYXRlcyBhIG1lYW5zIGV4cHJlc3Npb24gbGV2ZWwgZm9yIGVhY2ggZ2VuZS4gVGhlc2UgYXJlIG9yaWdpbmFsbHkgY2hvc2VuIGZyb20gYSBHYW1tYSBkaXN0cmlidXRpb24uCgpGaXJzdCBsZXQgc2VlIHRoZSBlZmZlY3Qgb2YgKmFscGhhKiBvciAqc2hhcGUqIChgbWVhbi5zaGFwZWAgcGFyYW1ldGVyKSBhbmQgKmJldGEqIG9yICpyYXRlKiAoYG1lYW4ucmF0ZWAgcGFyYW1ldGVyKSBvbiB0aGUgR2FtbWEgZGlzdHJpYnV0aW9uIGRlbnNpdHkKCmBgYHtyIGdhbW1hfQp0aWJibGUoCiAgYWxwaGEgPSBzZXEoZnJvbSA9IDEsIHRvID0gMTAsIGxlbmd0aC5vdXQgPSA1KQopICU+JSAKICBtdXRhdGUoCiAgICBiZXRhID0gbGlzdChzZXEoZnJvbSA9IDAuMSwgdG8gPSAwLjksIGxlbmd0aC5vdXQgPSA1KSkKICApICU+JSAKICB1bm5lc3QoYmV0YSkgJT4lIAogIG11dGF0ZSgKICAgIGxhbWJkYSA9IG1hcDIoYWxwaGEsIGJldGEsIGZ1bmN0aW9uKHgsIHkpewogICAgICByZ2FtbWEobiA9IDEwMDAsIHNoYXBlID0geCwgcmF0ZSA9IHkpCiAgICB9KQogICkgJT4lIAogIHVubmVzdChsYW1iZGEpICU+JSAKICBnZ3Bsb3QoYWVzKHggPSBsYW1iZGEpKSArCiAgZ2VvbV9oaXN0b2dyYW0oYmlud2lkdGggPSAxKSArCiAgZmFjZXRfd3JhcCh+YWxwaGEgKyBiZXRhLCBzY2FsZXMgPSAiZnJlZSIsIGxhYmVsbGVyID0gbGFiZWxfYm90aCkgKwogIHRoZW1lX2NsYXNzaWMoKQpgYGAKClRoZW4gbGV0IHNlZSB0aGUgZWZmZWN0IG9mIHRoZSAqc2hhcGUqIGFuZCAqcmF0ZSogcGFyYW1ldGVyIG9uIHRoZSBHYW1tYS1Qb2lzc29uIGRpc3RyaWJ1dGlvbiBkZW5zaXR5LgoKYGBge3IgZ2FtbWFfcG9pc3Nvbn0KdGliYmxlKAogIGFscGhhID0gc2VxKGZyb20gPSAxLCB0byA9IDEwLCBsZW5ndGgub3V0ID0gNSkKKSAlPiUgCiAgbXV0YXRlKAogICAgYmV0YSA9IGxpc3Qoc2VxKGZyb20gPSAwLjEsIHRvID0gMC45LCBsZW5ndGgub3V0ID0gNSkpCiAgKSAlPiUgCiAgdW5uZXN0KGJldGEpICU+JSAKICBtdXRhdGUoCiAgICBjb3VudCA9IG1hcDIoYWxwaGEsIGJldGEsIGZ1bmN0aW9uKHgsIHkpewogICAgIHJnYW1tYShuID0gMTAwMCwgc2hhcGUgPSB4LCByYXRlID0geSkgJT4lICAKICAgICAgbWFwX2RibChmdW5jdGlvbih4KXtycG9pcyhuID0gMSwgbGFtYmRhID0geCl9KQogICAgfSkKICApICU+JSAKICB1bm5lc3QoY291bnQpICU+JSAKICBnZ3Bsb3QoYWVzKHggPSBjb3VudCkpICsKICBnZW9tX2hpc3RvZ3JhbShiaW53aWR0aCA9IDEpICsKICBmYWNldF93cmFwKH5hbHBoYSArIGJldGEsIHNjYWxlcyA9ICJmcmVlIiwgbGFiZWxsZXIgPSBsYWJlbF9ib3RoKSArCiAgdGhlbWVfY2xhc3NpYygpCmBgYAoKPiBXaHkgZG8geW91IHRoaW5rIHRoYXQgYSBHYW1tYS1Qb2lzc29uIGlzIG1vcmUgcmVhbGlzdGljIHRoYW4gYSBQb2lzc29uIGRpc3RyaWJ1dGlvbiBmb3IgYSAKPiBnaXZlbiBnZW5lIGFuZCBhIGhvbW9nZW5lb3VzIHBvcHVsYXRpb24gb2YgY2VsbHMgPwoKPiBEbyB5b3Uga25vdyBhbm90aGVyIGRpc3RyaWJ1dGlvbiBuYW1lIHRoYXQgY2FuIGNvcnJlc3BvbmQgdG8gdGhpcyBraW5kIG9mIGRhdGEgPwoKVG8gYmV0dGVyIHVuZGVyc3RhbmQgd2hhdCB3ZSBhcmUgZG9pbmcgd2UgYXJlIGdvaW5nIHRvIGZpcnN0IHdvcmsgd2l0aCAyMDAwIGdlbmUgYW5kIDEwMDAgY2VsbHM6CgpgYGB7ciBwYXJtYXNfbmdlbmV9CnBhcmFtcyA8LSBzZXRQYXJhbShwYXJhbXMsICJuR2VuZXMiLCAyMDAwKQpwYXJhbXMgPC0gc2V0UGFyYW0ocGFyYW1zLCAiYmF0Y2hDZWxscyIsIDEwMDApCmBgYAoKRm9yIHNvbWUgZ2VuZXMgdGhhdCBhcmUgc2VsZWN0ZWQgdG8gYmUgb3V0bGllcnMgd2l0aCBoaWdoIGV4cHJlc3Npb24sIGEgZmFjdG9yIGlzIGdlbmVyYXRlZCBmcm9tIGEgbG9nLW5vcm1hbCBkaXN0cmlidXRpb24uIFRoZXNlIGZhY3RvcnMgYXJlIHRoZW4gbXVsdGlwbGllZCBieSB0aGUgbWVkaWFuIGdlbmUgbWVhbiB0byBjcmVhdGUgbmV3IG1lYW5zIGZvciB0aG9zZSBnZW5lcy4KCmBgYHtyIHBhcm1hc19vdXRsaWVyc30KIyBGZXcgb3V0bGllcnMKc2ltMSA8LSBzcGxhdFNpbXVsYXRlKG91dC5wcm9iID0gMC4wMDEsIHZlcmJvc2UgPSBGQUxTRSkKZ2dwbG90KGFzLmRhdGEuZnJhbWUocm93RGF0YShzaW0xKSksCiAgICAgYWVzKHggPSBsb2cxMChHZW5lTWVhbiksIGZpbGwgPSBPdXRsaWVyRmFjdG9yICE9IDEpKSArCiAgZ2VvbV9oaXN0b2dyYW0oYmlucyA9IDEwMCkgKwogIGdndGl0bGUoIkZldyBvdXRsaWVycyIpICsKICB0aGVtZV9jbGFzc2ljKCkKIyBMb3RzIG9mIG91dGxpZXJzCnNpbTIgPC0gc3BsYXRTaW11bGF0ZShvdXQucHJvYiA9IDAuMiwgdmVyYm9zZSA9IEZBTFNFKQpnZ3Bsb3QoYXMuZGF0YS5mcmFtZShyb3dEYXRhKHNpbTIpKSwKICAgICBhZXMoeCA9IGxvZzEwKEdlbmVNZWFuKSwgZmlsbCA9IE91dGxpZXJGYWN0b3IgIT0gMSkpICsKICBnZW9tX2hpc3RvZ3JhbShiaW5zID0gMTAwKSArCiAgZ2d0aXRsZSgiTG90cyBvZiBvdXRsaWVycyIpICsKICB0aGVtZV9jbGFzc2ljKCkKYGBgCgoKVGhlIGxpYnJhcnkgc2l6ZXMgYXJlIHRoZW4gdXNlZCB0byBzY2FsZSB0aGUgZ2VuZSBtZWFucyBmb3IgZWFjaCBjZWxsLCByZXN1bHRpbmcgaW4gYSByYW5nZSBhIGNvdW50cyBwZXIgY2VsbCBpbiB0aGUgc2ltdWxhdGVkIGRhdGFzZXQuIFRoZSBnZW5lIG1lYW5zIGFyZSB0aGVuIGZ1cnRoZXIgYWRqdXN0ZWQgdG8gZW5mb3JjZSBhIHJlbGF0aW9uc2hpcCBiZXR3ZWVuIHRoZSBtZWFuIGV4cHJlc3Npb24gbGV2ZWwgYW5kIHRoZSB2YXJpYWJpbGl0eS4KCj4gV2hhdCBpcyBhICpsaWJyYXJ5KiBpbiBzY1JOQS1TZXEgY29tcGFyZWQgdG8gYnVsayBSTkEtU2VxID8KClRoZSBgbGliLmxvY2AsIGBsaWIuc2NhbGVgIGRlZmluZSB0aGUgbWVhbiBhbmQgc3RhbmRhcmQgZGV2aWF0aW9uIG9mIHRoZSBsb2dOb3JtYWwgZGlzdHJpYnV0aW9uIGZyb20gd2hpY2ggaXMgZHJhd24gdGhlIGxpYnJhcnkgc2l6ZSBmYWN0b3IuCgpUaGUgZmluYWwgY2VsbCBieSBnZW5lIG1hdHJpeCBvZiBnZW5lcyBtZWFucyBpcyB0aGVuIHVzZWQgdG8gZ2VuZXJhdGUgYSBjb3VudCBtYXRyaXggdXNpbmcgYSBQb2lzc29uIGRpc3RyaWJ1dGlvbi4gVGhlIHJlc3VsdCBpcyBhIHN5bnRoZXRpYyBkYXRhc2V0IGNvbnNpc3Rpbmcgb2YgY291bnRzIGZyb20gYSBHYW1tYS1Qb2lzc29uIChvciBuZWdhdGl2ZS1iaW5vbWlhbCkgZGlzdHJpYnV0aW9uLiBBbiBhZGRpdGlvbmFsIG9wdGlvbmFsIHN0ZXAgY2FuIGJlIHVzZWQgdG8gcmVwbGljYXRlIGEg4oCcZHJvcG91dOKAnSBlZmZlY3QuIEEgcHJvYmFiaWxpdHkgb2YgZHJvcG91dCBpcyBnZW5lcmF0ZWQgdXNpbmcgYSBsb2dpc3RpYyBmdW5jdGlvbiBiYXNlZCBvbiB0aGUgdW5kZXJseWluZyBtZWFuIGV4cHJlc3Npb24gbGV2ZWwuIEEgQmVybm91bGxpIGRpc3RyaWJ1dGlvbiBpcyB0aGVuIHVzZWQgdG8gY3JlYXRlIGEgZHJvcG91dCBtYXRyaXggd2hpY2ggc2V0cyBzb21lIG9mIHRoZSBnZW5lcmF0ZWQgY291bnRzIHRvIHplcm8uCgpgYGB7ciBwYXJtYXNfZHJvcG91dH0KcGFyYW1zIDwtIHNldFBhcmFtKHBhcmFtcywgImRyb3BvdXQudHlwZSIsICJub25lIikKYGBgCgpUaGUgbW9kZWwgZGVzY3JpYmVkIGhlcmUgd2lsbCBnZW5lcmF0ZSBhIHNpbmdsZSBwb3B1bGF0aW9uIG9mIGNlbGxzIGJ1dCB0aGUgU3BsYXQgc2ltdWxhdGlvbiBoYXMgYmVlbiBkZXNpZ25lZCB0byBiZSBhcyBmbGV4aWJsZSBhcyBwb3NzaWJsZSBhbmQgY2FuIGNyZWF0ZSBzY2VuYXJpb3MgaW5jbHVkaW5nIG11bHRpcGxlIGdyb3VwcyBvZiBjZWxscyAoY2VsbCB0eXBlcyksIGNvbnRpbnVvdXMgcGF0aHMgYmV0d2VlbiBjZWxsIHR5cGVzIGFuZCBtdWx0aXBsZSBleHBlcmltZW50YWwgYmF0Y2hlcy4gVGhlIHBhcmFtZXRlcnMgdXNlZCB0byBjcmVhdGUgdGhlc2UgdHlwZXMgb2Ygc2ltdWxhdGlvbnMgYW5kIGhvdyB0aGV5IGludGVyYWN0IHdpdGggdGhlIG1vZGVsIGFyZSBkZXNjcmliZWQgYmVsb3cuCldlIHRoZW4gcmVtb3ZlIHRoZSBiYXRjaCBlZmZlY3QKCmBgYHtyIGZpcnN0X3NpbV9kYXRhfQpzaW0gPC0gc3BsYXRTaW11bGF0ZShwYXJhbXMpCmBgYAo+IFVzZSB0aGUgYHJvd0RhdGEoKWAgYW5kIGBjb2xEYXRhKClgIGZ1bmN0aW9uIHRvIGV4cGxvcmUgdGhlIGFkZGl0aW9uYWwgZGF0YSBzdG9yZWQgaW4gdGhlIGBzY2VgIGV4cGVyaW1lbnQgYnkgYHNwbGF0dGVyYAoKYGBge3IgcmF3X2NvbF9kYXRhfQpyb3dEYXRhKHNpbSkKY29sRGF0YShzaW0pCmBgYAoKIyMgRGF0YSB2aXN1YWxpemF0aW9uCgpXZSBjYW4gdXNlIGBzY2F0ZXJgIHRvIHZpc3VhbGl6ZSB0aGUgYHNpbWAgZGF0YQoKYGBge3Igc2ltX3BjYX0KIyBQQ0EgcGxvdCB1c2luZyBzY2F0ZXIKc2ltIDwtIGxvZ05vcm1Db3VudHMoc2ltKSAjIGFkZCBsb2cxcCBhc3NheQpzaW0gPC0gcnVuUENBKHNpbSkgIyBhZGQgUENBIHJlc3VsdHMgaW4gdGhlIGRpbWVuc2lvbiByZWR1Y3Rpb24gdGFibGVzCnBsb3RQQ0Eoc2ltLCBjb2xvdXJfYnkgPSAiQmF0Y2giKQpgYGAKCiMjIyBaZXJvcyBwbG90cwo+IFRyeSB0byByZXByb2R1Y2UgdGhlICoqMS40IFplcm9zKiogcGxvdCB1c2luZyB0aGUgYGNvdW50cygpYCBmdW5jdGlvbgoKV2UgYWRkIHRoZSBgemVyb19uYCBhbm5vdGF0aW9uIHRvIHRoZSBgc2NlYCBvYmplY3Q6CmBgYHtyIHplcm9fYW5ub3RhdGlvbl9yZWFsfQpyb3dEYXRhKHNpbSlbInplcm9fbiJdIDwtIHJvd1N1bXMoY291bnRzKHNpbSkgPT0gMCkKcm93RGF0YShzaW0pWyJzdW1fZ2VuZSJdIDwtIHJvd1N1bXMoY291bnRzKHNpbSkpCmNvbERhdGEoc2ltKVsiemVyb19uIl0gPC0gY29sU3Vtcyhjb3VudHMoc2ltKSA9PSAwKQpjb2xEYXRhKHNpbSlbInN1bV9jZWxsIl0gPC0gY29sU3Vtcyhjb3VudHMoc2ltKSkKYGBgCgpgYGB7ciB6ZXJvX3Bsb3RfY2VsbH0KY29sRGF0YShzaW0pICU+JSAKICBhc190aWJibGUoKSAlPiUgCiAgZ2dwbG90KGFlcyh4ID0gc3VtX2NlbGwsIHkgPSB6ZXJvX24pKSArCiAgZ2VvbV9wb2ludCgpICsKICBzY2FsZV94X2xvZzEwKCkgKwogIHRoZW1lX2NsYXNzaWMoKQpgYGAKCmBgYHtyIHplcm9fcGxvdF9nZW5lfQpyb3dEYXRhKHNpbSkgJT4lIAogIGFzX3RpYmJsZSgpICU+JSAKICBnZ3Bsb3QoYWVzKHggPSBzdW1fZ2VuZS8xMGUzLCB5ID0gemVyb19uKSkgKwogIGdlb21fcG9pbnQoKSArCiAgc2NhbGVfeF9sb2cxMCgpICsKICB0aGVtZV9jbGFzc2ljKCkKYGBgCgojIyMgUmVhbGlzdGljIHNpbXVsYXRpb24KClRvIHNpbXVsYXRlIGRhdGEgdGhhdCBsb29rIG1vcmUgbGlrZSByZWFsIG9uZSwgd2UgY2FuIHVzZSB0aGUgcGFyYW1ldGVycyBvZiBhIHJlYWwgZGF0YXNldC4KV2Ugc3RhcnQgYnkgZG93bmxvYWRpbmcgdGhlIGZvbGxvd2luZyAxMFggZ2Vub21pY3MgZGF0YXNldDoKCkluIHRoZSB0ZXJtaW5hbCBnZXQgdGhlIGRhdGEgc2V0OgoKYGBgc2gKd2dldCBodHRwczovL3MzLXVzLXdlc3QtMi5hbWF6b25hd3MuY29tLzEweC5maWxlcy9zYW1wbGVzL2NlbGwvcGJtYzNrL3BibWMza19maWx0ZXJlZF9nZW5lX2JjX21hdHJpY2VzLnRhci5negp0YXIgLXh2ZiBwYm1jM2tfZmlsdGVyZWRfZ2VuZV9iY19tYXRyaWNlcy50YXIuZ3oKYGBgCgpXZSB0aGVuIHVzZSB0aGlzIGRhdGEgc2V0IHRvIGNyZWF0ZSBhbiBgc2NlYCBvYmplY3QuIFdlIGFyZSBnb2luZyB0byB1c2UgdGhpcyBgc2NlYCBvYmplY3QgdG8gZXN0aW1hdGUgZ2VvbG9naWNhbGx5IHJlbGV2YW50IHBhcmFtZXRlcnMgZm9yIG91ciBzaW11bGF0ZWQgZGF0YS4KCmBgYHtyIGxvYWRfZGF0YX0Kc2NlIDwtIFNpbmdsZUNlbGxFeHBlcmltZW50KAogIFNldXJhdDo6UmVhZDEwWChkYXRhLmRpciA9ICJmaWx0ZXJlZF9nZW5lX2JjX21hdHJpY2VzL2hnMTkvIikKKQpwYXJhbXNfcmVhbCA8LSBhc3NheShzY2UpICU+JSAKICBhcy5tYXRyaXgoKSAlPiUgCiAgdCgpICU+JSAKICBhcy5kYXRhLmZyYW1lKCkgJT4lIAogIHNhbXBsZV9uKDEwMCkgJT4lICMgc3Vic2FtcGxlIGNlbGwgdG8gYmUgZmFzdGVyCiAgdCgpICU+JSAKICBzcGxhdHRlcjo6c3BsYXRFc3RpbWF0ZSgpCmBgYAoKV2UgY2FuIHRoZW4gc2ltdWxhdGUgb3VyIGRhdGEKCmBgYHtyIHNlY29uZF9zaW1fZGF0YX0Kc2ltIDwtIHNwbGF0U2ltdWxhdGUocGFyYW1zX3JlYWwsIG5HZW5lcyA9IDIwMDAsIGJhdGNoQ2VsbHMgPSAxMDAwLCB2ZXJib3NlID0gRikKYGBgCgo+IElzIHRoZSBjZWxscyBwbG90IG1vcmUgcmVhbGlzdGljID8KCmBgYHtyIHplcm9fYW5ub3RhdGlvbn0Kcm93RGF0YShzaW0pWyJ6ZXJvX24iXSA8LSByb3dTdW1zKGNvdW50cyhzaW0pID09IDApCnJvd0RhdGEoc2ltKVsic3VtX2dlbmUiXSA8LSByb3dTdW1zKGNvdW50cyhzaW0pKQpjb2xEYXRhKHNpbSlbInplcm9fbiJdIDwtIGNvbFN1bXMoY291bnRzKHNpbSkgPT0gMCkKY29sRGF0YShzaW0pWyJzdW1fY2VsbCJdIDwtIGNvbFN1bXMoY291bnRzKHNpbSkpCgpjb2xEYXRhKHNpbSkgJT4lIAogIGFzX3RpYmJsZSgpICU+JSAKICBnZ3Bsb3QoYWVzKHggPSBzdW1fY2VsbCwgeSA9IHplcm9fbikpICsKICBnZW9tX3BvaW50KCkgKwogIHNjYWxlX3hfbG9nMTAoKSArCiAgdGhlbWVfY2xhc3NpYygpCmBgYAoKIyMjIENvZWZmaWNpZW50IG9mIFZhcmlhdGlvbiBwbG90CgpGaW5hbGx5IGxldCdzIGNoZWNrIHRoZSBtZWFuIHZlcnN1cyBDViB2YXJpYXRpb24KCmBgYHtyIG1lYW5fQ1Z9CnJvd0RhdGEoc2ltKVsibWVhbiJdIDwtIHJvd01lYW5zKGNvdW50cyhzaW0pKQpyb3dEYXRhKHNpbSlbInZhciJdIDwtIHJvd1ZhcnMoY291bnRzKHNpbSkpCnJvd0RhdGEoc2ltKVsiQ1YiXSA8LSByb3dEYXRhKHNpbSlbInZhciJdWywgMV0gLyByb3dEYXRhKHNpbSlbIm1lYW4iXVssIDFdCgpyb3dEYXRhKHNpbSkgJT4lIAogIGFzX3RpYmJsZSgpICU+JSAKICBnZ3Bsb3QoYWVzKHggPSBtZWFuLCB5ID0gQ1YpKSArCiAgZ2VvbV9wb2ludCgpICsKICBzY2FsZV94X2xvZzEwKCkgKwogIGdlb21faGxpbmUoeWludGVyY2VwdCA9IDEsIGNvbG9yID0gInJlZCIpICsKICB0aGVtZV9jbGFzc2ljKCkKcm93RGF0YShzaW0pICU+JSAKICBhc190aWJibGUoKSAlPiUgCiAgZ2dwbG90KGFlcyh4ID0gbWVhbiwgeSA9IHZhcikpICsKICBnZW9tX3BvaW50KCkgKwogIHNjYWxlX3lfbG9nMTAoKSArCiAgc2NhbGVfeF9sb2cxMCgpICsKICBnZW9tX2FibGluZSh5aW50ZXJjZXB0ID0gMCwgc2xvcCA9IDEsIGNvbG9yID0gInJlZCIpICsKICB0aGVtZV9jbGFzc2ljKCkKYGBgCgo+IFdoYXQgY2FuIHlvdSB0ZWxsIGFib3V0IHRoaXMgcmVsYXRpb24gPwo+IFdoYXQgaXMgdGhlIGxpbmsgd2l0aCB0aGUgR2FtbWEtUG9pc3NvbiBtb2RlbCA/CgojIyBHcm91cHMgb2YgY2VsbHMKCkluIHJlYWwgZGF0YSBzZXQsIHdlIG9mdGVuIGhhdmUgZGlmZmVyZW50IGNlbGwgdHlwZXMgaW4gYSBkYXRhIHNldC4KSW4gYSBjbGFzc2ljYWwgYW5hbHlzaXMsIHlvdSBhcmUgZ29pbmcgdG8gaGF2ZSB0byBpZGVudGlmeSB0aGVzZSBncm91cHMgIChjbHVzdGVyaW5nKSBhbmQgZG8gdmFyaW91cyBhbmFseXNlcyBiZXR3ZWVuIHRoZXNlIGdyb3VwcyAoZGlmZmVyZW50aWFsIGV4cHJlc3Npb24gYW5hbHlzaXMsIGV0Yy4pLgoKV2UgY2FuIHVzZSBgc3BsYXR0ZXJgIHRvIHNpbXVsYXRlIGdyb3Vwcy4KClRoZSBgc3BsYXRTaW11bGF0ZUdyb3VwcygpYCBmdW5jdGlvbiBjYW4gdGFrZSB0aGUgZm9sbG93aW5nIHBhcmFtZXRlcnM6CgotIGBncm91cC5wcm9iYCBpcyBhIHZlY3RvciBvZiBncm91cCBwcm9wb3J0aW9uIHRoYXQgc3VtIHRvIDEKLSBgZGUucHJvYmAgaXMgdGhlIHByb3BvcnRpb24gb2YgZGlmZmVyZW50aWFsbHkgZXhwcmVzc2VkIGdlbmVzIGluIGVhY2ggZ3JvdXAKLSBgZGUuZG93blByb2JgIGlzIHRoZSBwcm9wb3J0aW9uIG9mIGRvd24tcmVndWxhdGVkIGdlbmVzIGluIGVhY2ggZ3JvdXAKLSBgZGUuZmFjTG9jYCBpcyB0aGUgbG9jYXRpb24gdmFsdWUgZm9yIGVhY2ggZ3JvdXAKLSBgZGUuZmFjU2FjbGVgIGlzIHRoZSBzY2FsZSB2YWx1ZSBmb3IgZWFjaCBncm91cAoKPiBUcnkgdG8gY2hhbmdlIHRoZSBgc3BsYXRTaW11bGF0ZUdyb3VwcygpYCBwYXJhbWV0ZXJzIHRvIHNlZSB0aGVpciBlZmZlY3Qgb24gdGhlIFBDQSByZXByZXNlbnRhdGlvbgoKYGBge3Igc2ltX2dyb3Vwc30Kc2ltIDwtIHNwbGF0U2ltdWxhdGVHcm91cHMocGFyYW1zLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgYmF0Y2hDZWxscyA9IDUwMCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIG5HZW5lcyA9IDEwMDAsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBncm91cC5wcm9iID0gYygwLjA1LCAwLjIsIDAuMiwgMC4yLCAwLjM1KSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGRlLnByb2IgPSBjKDAuMywgMC4xLCAwLjIsIDAuMDEsIDAuMSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBkZS5kb3duUHJvYiA9IGMoMC4xLCAwLjQsIDAuOSwgMC42LCAwLjUpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgdmVyYm9zZSA9IEZBTFNFKQpzaW0gPC0gbG9nTm9ybUNvdW50cyhzaW0pCnNpbSA8LSBydW5QQ0Eoc2ltKQpwbG90UENBKHNpbSwgY29sb3VyX2J5ID0gIkdyb3VwIikgKwogICAgbGFicyh0aXRsZSA9ICJEaWZmZXJlbnQgREUgZmFjdG9ycyIsCiAgICAgICAgIGNhcHRpb24gPSBwYXN0ZSgKICAgICAgICAgICAgICJHcm91cCAxIGlzIHNtYWxsIHdpdGggbWFueSB2ZXJ5IHVwLXJlZ3VsYXRlZCBERSBnZW5lcywiLAogICAgICAgICAgICAgIkdyb3VwIDIgaGFzIHRoZSBkZWZhdWx0IERFIHBhcmFtZXRlcnMsXG4iLAogICAgICAgICAgICAgIkdyb3VwIDMgaGFzIG1hbnkgZG93bi1yZWd1bGF0ZWQgREUgZ2VuZXMsIiwKICAgICAgICAgICAgICJHcm91cCA0IGhhcyB2ZXJ5IGZldyBERSBnZW5lcywiLAogICAgICAgICAgICAgIkdyb3VwIDUgaXMgbGFyZ2Ugd2l0aCBtb2RlcmF0ZSBERSBmYWN0b3JzIikKICAgICAgICAgKQpgYGAKCiMjIFBhdGhzIG9mIGNlbGxzCgpTb21ldGltZSwgaW4gc2NSTkEtU2VxIGluc3RlYWQgb2YgaGF2aW5nIGRpc2NyZWV0IGNlbGwtdHlwZSB3ZSBvYnNlcnZlIGEgY29udGludW91cyBwYXRoIG9mIGNlbGwgc3RhdGUuIFRoaXMgaXMgdGhlIGNhc2UgZm9yIGNlbGwgZGlmZmVyZW50aWF0aW9uLCBmb3IgZXhhbXBsZS4KCldlIGNhbiB1c2UgYHNwbGF0dGVyYCB0byBzaW11bGF0ZSBwYXRocy4KClRoZSBgc3BsYXRTaW11bGF0ZUdyb3VwcygpYCBmdW5jdGlvbiBjYW4gdGFrZSB0aGUgZm9sbG93aW5nIHBhcmFtZXRlcnM6CgotIGBwYXRoLmZyb21gIGlzIGEgdmVjdG9yIG9mIHRoZSBncm91cCBvcmRlciAoc3RhdGluZyBmcm9tIHplcm8pCgpgYGB7ciBzaW1fcGF0aH0Kc2ltIDwtIHNwbGF0U2ltdWxhdGVQYXRocyhwYXJhbXMsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBiYXRjaENlbGxzID0gNTAwLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgbkdlbmVzID0gMTAwMCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgZ3JvdXAucHJvYiA9IGMoMC4yNSwgMC4yNSwgMC4yNSwgMC4yNSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgIGRlLnByb2IgPSAwLjgsIGRlLmZhY0xvYyA9IDAuMiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgcGF0aC5mcm9tID0gYygwLCAxLCAyLCAzKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgdmVyYm9zZSA9IEZBTFNFKQpzaW0gPC0gbG9nTm9ybUNvdW50cyhzaW0pCnNpbSA8LSBydW5QQ0Eoc2ltKQpwbG90UENBKHNpbSwgY29sb3VyX2J5ID0gIkdyb3VwIikgKyBnZ3RpdGxlKCJMaW5lYXIgcGF0aHMiKQpgYGAKCiMjIEJhdGNoZXMKCkZpbmFsbHksIGluIHNvbWUgZXhwZXJpbWVudCwgdGhlIG51bWJlciBvZiBjZWxscyBpcyB0b28gaGlnaCB0byBiZSBzZXF1ZW5jZWQgaW4gb25lIGdvLgpGb3IgdGhlc2UgZGF0YXNldHMgeW91IHdpbGwgaGF2ZSBiYXRjaCBlZmZlY3RzLgoKSW4gYHNwbGF0dGVyYCwgSWYgeW91IGdpdmUgYSB2ZWN0b3Igb2YgaW50ZWdlcnMgdG8gdGhlIGBiYXRjaENlbGxzYCBwYXJhbWV0ZXJzLCB5b3Ugd2lsbCBzaW11bGF0ZSBiYXRjaGVzLgoKYGBge3Igc2ltX2dyb3Vwc19iYXRjaGVzfQpzaW0gPC0gc3BsYXRTaW11bGF0ZUdyb3VwcyhwYXJhbXMsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBiYXRjaENlbGxzID0gYyg1MDAsIDUwMCksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBuR2VuZXMgPSAxMDAwLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgZ3JvdXAucHJvYiA9IGMoMC4wNSwgMC4yLCAwLjIsIDAuMiwgMC4zNSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBkZS5wcm9iID0gYygwLjMsIDAuMSwgMC4yLCAwLjAxLCAwLjEpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgZGUuZG93blByb2IgPSBjKDAuMSwgMC40LCAwLjksIDAuNiwgMC41KSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHZlcmJvc2UgPSBGQUxTRSkKc2ltIDwtIGxvZ05vcm1Db3VudHMoc2ltKQpzaW0gPC0gcnVuUENBKHNpbSkKcGxvdFBDQShzaW0sIGNvbG91cl9ieSA9ICJHcm91cCIsIHNoYXBlX2J5ID0gIkJhdGNoIikgKwogICAgbGFicyh0aXRsZSA9ICJEaWZmZXJlbnQgREUgZmFjdG9ycyIsCiAgICAgICAgIGNhcHRpb24gPSBwYXN0ZSgKICAgICAgICAgICAgICJHcm91cCAxIGlzIHNtYWxsIHdpdGggbWFueSB2ZXJ5IHVwLXJlZ3VsYXRlZCBERSBnZW5lcywiLAogICAgICAgICAgICAgIkdyb3VwIDIgaGFzIHRoZSBkZWZhdWx0IERFIHBhcmFtZXRlcnMsXG4iLAogICAgICAgICAgICAgIkdyb3VwIDMgaGFzIG1hbnkgZG93bi1yZWd1bGF0ZWQgREUgZ2VuZXMsIiwKICAgICAgICAgICAgICJHcm91cCA0IGhhcyB2ZXJ5IGZldyBERSBnZW5lcywiLAogICAgICAgICAgICAgIkdyb3VwIDUgaXMgbGFyZ2Ugd2l0aCBtb2RlcmF0ZSBERSBmYWN0b3JzIikKICAgICAgICAgKQpgYGAKCj4gQ2xpY2sgb24gdGhlIFtOZXh0XSguL3JuYV9xdWFudGlmaWNhdGlvbi5uYi5odG1sKSBsaW5r